6 ms·

It's nice to recover an image but encryption keys are not that. One bit flip and it's game over. This experiment is more useful for human-readable document fore

It's nice to recover an image but encryption keys are not that. One bit flip and it's game over. This experiment is more useful for human-readable document forensics than anything else.

dist-epoch 3y ago
If from a 128 bit key 120 are correct, it's trivial to figure out the others, even if you don't know which bits are the flipped ones. Cryptographers worry even when a few key bits are leaked.
- tczMUFlmoNk 3y ago
  > If from a 128 bit key 120 are correct, it's trivial to figure out the others, even if you don't know which bits are the flipped ones. Can you elaborate a bit? Off the top of my head, I feel like that scenario would leave 128-choose-8 possibilities open, or about 1.4 trillion. Are we calling that "trivial" or am I misunderstanding the attack? (If you're calling that "trivial", I think that could be reasonable in a cryptography context where you're considering attackers with a lot of resources. It's just different from how I usually use that word. I don't disagree with your conclusion that leakage of even a few bits is worth worrying about.)
  - IanCal 3y ago
    If it's 1.4T it depends on what you're using it for. Someone on SO has a verify speed for 512 bit rsa keys at 350k/second which would leave it at I think a month and a half to run 1.4T. That's a random user and a single machine. ECDSA 128 bit verify maybe 6k/s on a single core of a not-great CPU. That puts you about a month or two of a moderate machine assuming there's no fancy gpu things for doing it.
    - dist-epoch 3y ago
      These are symmetric keys - AES, not ECDSA. Much faster to test.
  - dist-epoch 3y ago
    A NVIDIA 3090 with HashCat can do 3 billion AES decryptions per second. That would test all 1.4 trillion in less than an hour.
  - cloudbonsai 3y ago
    > scenario would leave 128-choice-8 possibilities open That only amounts to log2(C(128, 8)) ~= 40.3. Your encryption key is now just 40-bit strength.
PrimeMcFly 3y ago
a passphrase is much shorter than a key and may be in memory multiple times.
orlp 3y ago
Alright let's test this hypothesis. Load up a bitcoin wallet and post the private key here with 1 random bit flip :)
- Cheer2171 3y ago
  You might think you're being clever, but specifying exactly 1 random bit flip makes it a completely different scenario.
  - krab 3y ago
    If you can reliably find the key in memory, even if it's partially damaged, it may practically possible to recover it. You can try keys sorted by edit distance from the recovered material. Maybe there are better methods taking into account the actual cryptography.
  - ivancho 3y ago
    The original comment said "One bit flip and it's game over". Which is clear nonsense, I don't have to specify that there's exactly one bit flip, I just need to know that the key is in that general neighborhood and its security is already compromised.
- matheusmoreira 3y ago
  If you just recovered a secret key, you have no idea how many bits were flipped or their positions or if they were flipped at all or even it if it's actually a key rather than random garbage data. Key strength is therefore maintained. Posting a secret key here and specifying "exactly one bit was flipped" reduces the problem to N guesses where N is the key length since you know all the other N - 1 bits are correct. Leaking just a few bits has catastrophic consequences, in your example all bits except one are leaked.
  - ivancho 3y ago
    You can't simultaneously have that key strength is maintained as long as they don't know how many bits are flipped, or where in memory the key was, but also that leaking any number of bits is catastrophic. If your memory dump creates a different distribution on the space of possible keys, it has already compromised the cryptographic security of the key, it's just a question of how much, and the answer here is a lot - even if we had GBs of garbage data, that is still tiny compared to the whole space and can be sifted extremely quickly

It's nice to recover an image but encryption keys are not that. One bit flip and it's game over. This experiment is more useful for human-readable document forensics than anything else.

dist-epoch 3y ago

If from a 128 bit key 120 are correct, it's trivial to figure out the others, even if you don't know which bits are the flipped ones. Cryptographers worry even when a few key bits are leaked.

tczMUFlmoNk 3y ago
> If from a 128 bit key 120 are correct, it's trivial to figure out the others, even if you don't know which bits are the flipped ones. Can you elaborate a bit? Off the top of my head, I feel like that scenario would leave 128-choose-8 possibilities open, or about 1.4 trillion. Are we calling that "trivial" or am I misunderstanding the attack? (If you're calling that "trivial", I think that could be reasonable in a cryptography context where you're considering attackers with a lot of resources. It's just different from how I usually use that word. I don't disagree with your conclusion that leakage of even a few bits is worth worrying about.)
- IanCal 3y ago
  If it's 1.4T it depends on what you're using it for. Someone on SO has a verify speed for 512 bit rsa keys at 350k/second which would leave it at I think a month and a half to run 1.4T. That's a random user and a single machine. ECDSA 128 bit verify maybe 6k/s on a single core of a not-great CPU. That puts you about a month or two of a moderate machine assuming there's no fancy gpu things for doing it.
  - dist-epoch 3y ago
    These are symmetric keys - AES, not ECDSA. Much faster to test.
- dist-epoch 3y ago
  A NVIDIA 3090 with HashCat can do 3 billion AES decryptions per second. That would test all 1.4 trillion in less than an hour.
- cloudbonsai 3y ago
  > scenario would leave 128-choice-8 possibilities open That only amounts to log2(C(128, 8)) ~= 40.3. Your encryption key is now just 40-bit strength.

PrimeMcFly 3y ago

a passphrase is much shorter than a key and may be in memory multiple times.

orlp 3y ago

Alright let's test this hypothesis. Load up a bitcoin wallet and post the private key here with 1 random bit flip :)

Cheer2171 3y ago
You might think you're being clever, but specifying exactly 1 random bit flip makes it a completely different scenario.
- krab 3y ago
  If you can reliably find the key in memory, even if it's partially damaged, it may practically possible to recover it. You can try keys sorted by edit distance from the recovered material. Maybe there are better methods taking into account the actual cryptography.
- ivancho 3y ago
  The original comment said "One bit flip and it's game over". Which is clear nonsense, I don't have to specify that there's exactly one bit flip, I just need to know that the key is in that general neighborhood and its security is already compromised.
matheusmoreira 3y ago
If you just recovered a secret key, you have no idea how many bits were flipped or their positions or if they were flipped at all or even it if it's actually a key rather than random garbage data. Key strength is therefore maintained. Posting a secret key here and specifying "exactly one bit was flipped" reduces the problem to N guesses where N is the key length since you know all the other N - 1 bits are correct. Leaking just a few bits has catastrophic consequences, in your example all bits except one are leaked.
- ivancho 3y ago
  You can't simultaneously have that key strength is maintained as long as they don't know how many bits are flipped, or where in memory the key was, but also that leaking any number of bits is catastrophic. If your memory dump creates a different distribution on the space of possible keys, it has already compromised the cryptographic security of the key, it's just a question of how much, and the answer here is a lot - even if we had GBs of garbage data, that is still tiny compared to the whole space and can be sifted extremely quickly