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.
_______________________________________________
tahoe-dev mailing list
[email protected]
http://allmydata.org/cgi-bin/mailman/listinfo/tahoe-dev
