3 ms·

Can anybody ELI5?

by fergie 3y ago

Can anybody ELI5?

blueflow 3y ago
Random hardware bit flips can cause invalid RSA signatures, which baddies can use to deduce private keys. Edit: Don't ask me questions, i don't know shit, i just rephrased stuff from the linked paper.
- yard2010 3y ago
  What are the methods used by these baddies?
- clbrmbr 3y ago
  How frequently do such faults occur?
  - temac 3y ago
    Virtually never in practice (they are corrected) if you use ECC. A server that doesn't is weird. TBH any computer that doesn't is weird but the industry seems to consider it normal to have random computational unreliability because of that pretty much only unprotected component (Ram without ECC) in consumer hw.
  - sebstefan 3y ago
    > We also carry out a retrospective analysis of historical SSH scan data collected over the course of seven years, and find that these invalid signatures and vulnerable devices are surprisingly common over time. > Our combined dataset of around 5.2 billion SSH records contained more than 590,000 invalid RSA signatures. Seems like over long periods, it can occur a spoopy amount of time.
- mackman 3y ago
  Does each bit flip reveal a bit or less or does somehow a single flip compromise the entire key?
  - SAI_Peregrinus 3y ago
    A single bit flip reveals the entire private key, for RSA with PKCS#1v1.5. RSA with PKCS#1v2 (aka RSA-PSS) is not vulnerable.
  - sebstefan 3y ago
    It's akin to me having the secret number 17, giving you 221 (17*13) and then, during a solar flare, fucking it up once and giving you 187 (17*11). You know that the numbers are the product of a multiplication, and you know that a common factor is my private secret number. You figure out that the only way to get to 187 and 221 while keeping a common factor is if that factor is 17. That's just computing the GCD. >An RSA public key consists of a public exponent 𝑒 and a modulus 𝑁 = 𝑝𝑞 that is the product of two primes. The private key consists of the private exponent 𝑑 = 𝑒 −1 mod 𝜙 (𝑁) and 𝑁 . A textbook RSA signature on a message 𝑚 is the value 𝑠 = 𝑚𝑑 mod 𝑁 . To verify the signature, a user checks if 𝑠𝑒 mod 𝑁 = 𝑚 > these attacks exploit the fact that if an error is made while computing modulo one prime, say 𝑞, then the resulting invalid signature ˆ𝑠 is equivalent to the correct signature modulo one prime factor 𝑝, but not 𝑞. 2.2.1 GCD attack on fully known messages. Boneh, DeMillo, and Lipton noted [11] that if an attacker had a correct signature 𝑠 and an incorrect signature ˆ𝑠 of this form then the attacker could compute gcd(𝑁, ˆ𝑠 − 𝑠) = 𝑝
    - gonzo 3y ago
      you have to flip two bits to get from 13 (1101) to 11 (1011).
javajosh 3y ago
How about ELI precocious 10 year old? Cosmic rays and thermal effects cause random bit flips in memory very infrequently. If you sit on a network and listen to TLS handshakes for long enough, you'll find that any given server will issue the wrong signature occasionally, because of these bit flips. If you record the wrong signature(s) and use a fancy algorithm, you can recover the private key. While at first it may seem an unlikely attack, it's probably more real than you'd think, given the number of times any single server does TLS negotiation using a given private key. The attack becomes even more likely when you realize that multiple servers will be using the private key. In practice, this gives middle boxes more power, and raises their profile in the threat model significantly. This also opens up the possibility of simply collecting failed transient failed tls negotation data from a large number of (legitimate) clients to reconstruct a private key.
- gosub100 3y ago
  > Cosmic rays and thermal effects now put your tinfoil hat on and suppose you worked for a paramilitary organization that had infiltrated the top 2 semiconductor manufacturers. You persuade the silicon designers, when implementing hardware accelerated crypto (or "management engines") to not do their jobs quite perfectly, no just leave room for a tiny bit of....error. Could never happen, right?

Can anybody ELI5?

by fergie 3y ago

Can anybody ELI5?

Random hardware bit flips can cause invalid RSA signatures, which baddies can use to deduce private keys. Edit: Don't ask me questions, i don't know shit, i just rephrased stuff from the linked paper.

yard2010 3y ago
What are the methods used by these baddies?
clbrmbr 3y ago
How frequently do such faults occur?
- temac 3y ago
  Virtually never in practice (they are corrected) if you use ECC. A server that doesn't is weird. TBH any computer that doesn't is weird but the industry seems to consider it normal to have random computational unreliability because of that pretty much only unprotected component (Ram without ECC) in consumer hw.
- sebstefan 3y ago
  > We also carry out a retrospective analysis of historical SSH scan data collected over the course of seven years, and find that these invalid signatures and vulnerable devices are surprisingly common over time. > Our combined dataset of around 5.2 billion SSH records contained more than 590,000 invalid RSA signatures. Seems like over long periods, it can occur a spoopy amount of time.
mackman 3y ago
Does each bit flip reveal a bit or less or does somehow a single flip compromise the entire key?
- SAI_Peregrinus 3y ago
  A single bit flip reveals the entire private key, for RSA with PKCS#1v1.5. RSA with PKCS#1v2 (aka RSA-PSS) is not vulnerable.
- sebstefan 3y ago
  It's akin to me having the secret number 17, giving you 221 (17*13) and then, during a solar flare, fucking it up once and giving you 187 (17*11). You know that the numbers are the product of a multiplication, and you know that a common factor is my private secret number. You figure out that the only way to get to 187 and 221 while keeping a common factor is if that factor is 17. That's just computing the GCD. >An RSA public key consists of a public exponent 𝑒 and a modulus 𝑁 = 𝑝𝑞 that is the product of two primes. The private key consists of the private exponent 𝑑 = 𝑒 −1 mod 𝜙 (𝑁) and 𝑁 . A textbook RSA signature on a message 𝑚 is the value 𝑠 = 𝑚𝑑 mod 𝑁 . To verify the signature, a user checks if 𝑠𝑒 mod 𝑁 = 𝑚 > these attacks exploit the fact that if an error is made while computing modulo one prime, say 𝑞, then the resulting invalid signature ˆ𝑠 is equivalent to the correct signature modulo one prime factor 𝑝, but not 𝑞. 2.2.1 GCD attack on fully known messages. Boneh, DeMillo, and Lipton noted [11] that if an attacker had a correct signature 𝑠 and an incorrect signature ˆ𝑠 of this form then the attacker could compute gcd(𝑁, ˆ𝑠 − 𝑠) = 𝑝
  - gonzo 3y ago
    you have to flip two bits to get from 13 (1101) to 11 (1011).

javajosh 3y ago

How about ELI precocious 10 year old? Cosmic rays and thermal effects cause random bit flips in memory very infrequently. If you sit on a network and listen to TLS handshakes for long enough, you'll find that any given server will issue the wrong signature occasionally, because of these bit flips. If you record the wrong signature(s) and use a fancy algorithm, you can recover the private key. While at first it may seem an unlikely attack, it's probably more real than you'd think, given the number of times any single server does TLS negotiation using a given private key. The attack becomes even more likely when you realize that multiple servers will be using the private key. In practice, this gives middle boxes more power, and raises their profile in the threat model significantly. This also opens up the possibility of simply collecting failed transient failed tls negotation data from a large number of (legitimate) clients to reconstruct a private key.

gosub100 3y ago
> Cosmic rays and thermal effects now put your tinfoil hat on and suppose you worked for a paramilitary organization that had infiltrated the top 2 semiconductor manufacturers. You persuade the silicon designers, when implementing hardware accelerated crypto (or "management engines") to not do their jobs quite perfectly, no just leave room for a tiny bit of....error. Could never happen, right?