6
$\begingroup$

One of the most (in)famous hardware derived random number generators was Lavarand (patent). It did it with funky lava lamps. An image of the lamps was hashed and fed into Blum Blum Shub (BBS) to produce a cryptographic bit stream.

How? The patent refers to using NIST SHS-1 (SHA-1) which outputs a 160 bit hash. This seems to get reduced to multiple 140 bit hashes and then "The 140-byte value gets fed through the Blum Blum Shub[sic]". I thought that the seed for BBS was computed via prime multiplication. How can the seed (typically p.q) just be arbitrary hash output and still perform it's integer factorisation? BBS typically utilises a single state of 1000s of bits, not groups of 140. They did it like this which is a little lite on detail, and steps 3 & 4 from the archived web site don't clear it up any...

Patent, Fig. 6

I realise that this was all a long time ago. How can above steps 600 and 605 be connected together?

$\endgroup$
  • 2
    $\begingroup$ I'd probably use a camera and raspberry pi contraption, but it sounds like an idea some stoned hippies concocted. $\endgroup$ – Q-Club Apr 23 '17 at 0:07
6
$\begingroup$

I thought that the seed for BBS was computed via prime multiplication.

This is not how BBS works. To help better understand the seed, it's necessary to explain BBS.

Blum Blum Shub is realized in the form of $x_{i+1} = x^2_i \bmod N$. The initial seed, $x_0$, merely has to be co-prime to Blum primes $p$ and $q$ (where $N = p\cdot q$, making $N$ a Blum integer), and must not be $0$ or $1$. The seed is $x_0$, not $p$ and $q$ (which were likely generated once to create the hardcoded $N$ and then thrown away*). They are likely using the raw hash output as the seed, since it's unlikely that it won't be co-prime to $N$. They give you the modulus on the page you linked, but obviously not the primes:

5360751114622011236087979022735306713592537659947455285353148181
8526455500785383194936281698585494806464721601253386562653528822
5543322562532917886396992291116815877218495559211688377961466145
0857446201926232198015028137924055146650866097197909406089918491
4133568666470293429076893274969016410915119621659901793350665953

This is a 1062-bit modulus. Unfortunately, it seems that BBS can be broken up to $10^{54} n^3$ times faster than it takes to factor the $n$-bit modulus. This means that BBS used with their parameters can be broken $10^{54} \times 1062^3 \approx 1.20 \times 10^{63}$ times faster than it takes to factor the modulus, which is a significant enough speedup that the proof is completely broken. Additionally, that is only when a single bit is extracted from each $x_i$ (officially by taking the parity of $x_i$). If more bits are extracted at a time, it becomes even weaker. The moral is that parameters that seem acceptable are terrible for BBS.

The security proof for BBS is only a reduction to a problem with no known solution. That is, a correct implementation (i.e. one where only one bit is extracted from each $x_i$, and only when the modulus is "sufficiently" large) can only be broken if the quadratic residuosity problem (QRP) is solved. It is "proven secure" in the same way that RSA is "proven secure" because a proper implementation is provably reducible to the security of the RSA problem (the difficulty of finding the $e^\mathrm{th}$ root of an integer, modulo $N$), but no one thinks of RSA as having perfect security. In other words, BBS has a security reduction to a yet-unproven problem, not information-theoretic security. Competent developers do not use BBS.

How can above steps 600 and 605 be connected together?

Are you asking how the 140-byte seed comes from the 160-bit hash? That is actually answered in the link you provided. There are seven SHA-1s. The seventh hashes every seventh byte, the sixth hashes every sixth byte, etc. The bytes come from an image of the lava lamp itself. The final hash values are concatenated to form a 140-byte (1120-bit) value. This value is used, presumably directly, as $x_0$.

* The only thing you are losing by not having access to $p$ and $q$ is the ability to calculate any $x_i$ value directly from $x_0$ without having to calculate all of $x_1 \cdots x_{i-1}$ first by using Euler's theorem to do $x_i = (x_0^{2^i \bmod \lambda(N)}) \bmod N$ where $\lambda$ is the Carmichael totient function. If an attacker factors $N$, they are able to do this as well, breaking the security reduction.

† Broken in this context does not refer to the ability to predict the random stream or recover the seed. Instead, it means the security proof is invalidated and that the algorithm is no longer reducible to a known hard problem and that a break could exist which does not rely on solving QRP. Critically, it does not automatically imply that such a break does, in fact, exist.

‡ Although the quadratic residuosity problem is often thought to be as difficult as integer factorization, this has not been proven. It is possible that a method to break BBS could be exist which solves QRP without solving integer factorization.

$\endgroup$
  • 1
    $\begingroup$ At first glance, I do not understand the formerly linked article as stating that BBS can be broken $10^{54} n^3$ times easier than factoring. Rather, my understanding is that it shows that the common BBS security argument gives effectively no assurance that BBS can not be broken (for common parameters including extracting $\log(n)$ bits at each iteration), which is very different from stating that it could be broken, much less easily. $\endgroup$ – fgrieu Jul 3 '18 at 6:33
  • 1
    $\begingroup$ @fgrieu That is why I removed it and instead linked to the answer that cites it and two others. It's not that it breaks BBS so much as it breaks the security proof (i.e. the only thing that makes BBS even remotely attractive to the people who blindly decide to use it). $\endgroup$ – forest Jul 3 '18 at 6:35
  • $\begingroup$ The linked answer states that "[it was] found that it's possible that there could be an attack that breaks BBS and is $10^{54}*n^3$ times faster than any algorithm [..] for factoring the BBS modulus" (emphasis mine). I read it as meaning the researcher concludes there is no proof that there is no attack better than the stated bound, rather than in evidence of an attack approaching that bound. $\endgroup$ – fgrieu Jul 3 '18 at 6:48
  • $\begingroup$ @fgrieu Indeed. I did not mean to claim that recovering $x_0$ can be done that much faster, just that the security proof is broken. It may very well be that it is still secure, but there is no longer a reduction to QRP except at very, very tiny security levels. Should I edit my answer to make it more clear? $\endgroup$ – forest Jul 3 '18 at 6:51
  • 1
    $\begingroup$ @PaulUszak Are you asking how the 140 byte seed comes from the 160 bit hash? That is answered in the link you provided. There are seven SHA-1s. The seventh hashes every seventh byte, the sixth hashes every sixth byte, etc. The bytes come from an image of the lava lamp itself. The final hash values are concatenated to form a 140 byte (1120 bit) value. I described BBS to make it easier to understand exactly what the seed is (i.e. the initial starting value, not the primes). $\endgroup$ – forest Jul 3 '18 at 10:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.