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

[tahoe-lafs]

#217: DSA-based mutable files -- small URLs, fast file creation
----------------------------+-----------------------------------------------
 Reporter:  zooko           |           Owner:  zooko     
     Type:  enhancement     |          Status:  assigned  
 Priority:  major           |       Milestone:  eventually
Component:  code-mutable    |         Version:  0.7.0     
 Keywords:  mutable crypto  |   Launchpad_bug:            
----------------------------+-----------------------------------------------

Comment(by zooko):

 Shawn: thank you very much for this analysis.  I agree that it is an
 issue.  Ian Goldberg also pointed out this issue to me in private
 communication.  I made a mistake in
 [http://testgrid.allmydata.org:3567/file/URI:CHK:xugaee6vb725rmuv326vjp3tsq:qshdla2meskmu4n6mgg57ppez4cmxqlmj7hsqydjf2r5uzd6twca:3:10:275101/@@named=/lafs.pdf
 the paper] by saying {{{"let y = H(g^x)"}}}.  Instead, when you're
 generating a "random" or unguessable ECC point, you should choose an
 exponent in the interval {{{[0..n-1]}}} uniformly (where {{{n}}} is the
 order of the group).

 A typical way to do that is instead of taking the result {{{mod n}}}, you
 instead check whether the result is {{{>= n}}}, and if it is then "re-
 roll" for example by incrementing the input and trying again.  :-)  There
 is another way to do it which involves generating an extra 80 bits or so
 of your result and taking the whole thing {{{mod n}}}, in order to avoid
 the theoretically unbounded problem of re-rolling over and over, but that
 seems unnecessary to me, especially considering that the {{{n}}}'s that we
 are talking about often start with lots of leading 1 bits.  E.g., here is
 the order of the NIST 256-bit randomly-generated curve in hex:
 {{{0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551}}}.

 Anyway, we should amend the semi-private keys proposal which says {{{"let
 y = H(g^x)"}}} to define {{{H}}} as being "secure hash and then re-roll
 until it falls within the interval of {{{[0..n-1]}}}" instead opf being
 "secure hash and then {{{mod n}}}".

 That completely solves the weakness that you've identified, right Shawn?

 Thanks!

-- 
Ticket URL: <http://allmydata.org/trac/tahoe/ticket/217#comment:45>
tahoe-lafs <http://allmydata.org>
secure decentralized file storage grid