[dsfjdssdfsd] Blum-Blum-Shub ambiguity in 4086 ...

[Dan Brown <[e-mail]>]

Two issues:

 

1.      If it is unclear to me from the 4086 description of BBS whether the
state s_i is to be updated after each output. I believe that the state
should be updated to improve backtracking resistance.  (Otherwise, it would
be affected by a similar weak backtracking attack to the one DSS RNG, i.e.
current state compromise the latest output can be distinguished from
random.)

2.      Does the secret state include p and q?  If so, then the BBS suffers
from a more severe backtracking attack: recovering the current state allows
recovery of all the previous states, because p and q allows one to compute
square roots.  This would undermine forward security applications.

 

Best regards,

 


Daniel Brown


Research In Motion Limited