[tahoe-dev] #217: DSA-based mutable files -- small URLs, fast file creation

[Shawn Willden]

On Tuesday 03 February 2009 08:26:00 pm zooko wrote:
> It is the topic of section 6 of: http://allmydata.org/~zooko/lafs.pdf

Clever!  And quite simple and flexible, too.  I do see a weakness, though.

The security of DSA is dependent on x being drawn from a uniformly-distributed 
keyspace, but the distribution of xy mod q is not uniform.

If X and Y are uniform random variables (a reasonable assumption since secure 
hash functions are designed to simulate uniform random variables), then the 
PMF of XY mod q has a kind of a fractal-ish sawtooth wave shape.  I haven't 
found a way to characterize it mathematically, but I plotted some histograms 
to get an idea of the shape.  Ideally, you want every element of XY mod q to 
appear with probability 1/q.  In fact, based on some testing with tractable 
values of q, it appears that an attacker who searches the right 25% of the 
keyspace has a 50% chance of finding the key.

Some interesting patterns in the PMF, CMF and sorted CMF make me think it 
should be possible to find a simple mathematical description of the 
structure, which would enable quantitative analysis, including determination 
of the effective keyspace size.  How exactly to do that isn't obvious to me, 
though.  This stuff always makes me wish I'd bothered to take a course in 
statistics :-)

What is clear is that the construction is not as strong as normal DSA.  I'm 
not sure whether it weakens DSA enough to make a practical break feasible.  
My intuition says no, but intuition is pretty unreliable in this space. 

	Shawn.