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

[Jon Callas <[e-mail]>]

On Mar 17, 2014, at 7:42 AM, Dan Brown <[e-mail]> wrote:

> 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.
> 

Yes, it does suffer from that same problem. While BBS has number-theoretic proofs of security, those proofs presume a random, unknown p and q. I've said that this is pushing the randomness problem down to the turtle below you.

I wrote a missive on the Cryptography list around the turn of the year in which I said that the EC DRBGs have this problem -- you get randomness providing you have a secret key, but how did you get *that*? -- going back to BBS. If you want, I'll dredge it up and post here.

	Jon