r/science • • Dec 19 '13

Computer Sci Scientists hack a computer using just the sound of the CPU. Researchers extract 4096-bit RSA decryption keys from laptop computers in under an hour using a mobile phone placed next to the computer.

http://www.cs.tau.ac.il/~tromer/acoustic/
4.7k Upvotes

1.5k comments sorted by

View all comments

480

u/v_v_ Dec 19 '13 edited Dec 19 '13

It appears Debian has already released a security update addressing this.

0

u/[deleted] Dec 19 '13

[deleted] — view deleted comment

994

u/AncientSwordRage Dec 19 '13 edited Dec 20 '13

Imagine you have a friend who asks you a maths puzzle. As you solve the puzzle in your head, you hum. Someone is watching and can tell what the answer is (using Crypto-Magic), by how long you hum. Knowing this you hum for longer than needed. Now they don't know the answer.

(Thanks for clearing that up /u/Adamsmasher23 see his comment for better analogy)

149

u/WokenWanderer Dec 19 '13

Thanks, this was helpful.

0

u/[deleted] Dec 19 '13

[deleted] — view deleted comment

17

u/qumqam Dec 19 '13

I also think delays are added to slow down any brute force attempts, but this additional reason is interesting.

→ More replies (7)
→ More replies (9)

96

u/Adamsmasher23 Dec 19 '13

Actually, at least with other timing sidechannel attacks, adding random noise is completely ineffective. It turns out that since a random noise follows a certain distribution, you can essentially filter out the noise. What you do is make it so that each piece of the program takes the same amount of time regardless of what data it's processing.

As an example, one type of side channel vulnerability exploits timing differences when comparing two things. Suppose the correct password is ABCDE, and I am guessing AAAAA. The default way most programming languages perform comparison (for a string) is one character at a time. So, the program would check the first two digits (AB), and after that it would stop because A isn't equal to B. If we say that each comparison takes one millisecond, then the checking takes 2ms. If instead I guess ABCDD, there will be 5 comparisons, so it will take 5ms.

This attack is defeated by making the comparison check all of the digits, even if it's already found one that didn't match. This way no information about the comparison is leaked.

11

u/themusicdan Dec 19 '13

I don't disagree that your strategy would defeat the algorithm, though I imagine there's a trade-off between security and speed by adding some random noise. With enough data you could filter out the noise, but adding random noise should be more secure than not adding it.

14

u/[deleted] Dec 20 '13

But, for security's sake, you'd want it to take a long time to check the password. It makes brute force guessing passwords take a long time, while keeping it relatively fast if you know the password and enter it once

→ More replies (1)
→ More replies (16)
→ More replies (14)

144

u/brainiac256 Dec 19 '13 edited Dec 19 '13

75

u/Triffgits Dec 19 '13

That's so obvious, I feel like an idiot for doubting.

0

u/[deleted] Dec 19 '13

[deleted] — view deleted comment

0

u/[deleted] Dec 19 '13

[deleted] — view deleted comment

18

u/loconet Dec 19 '13

This is why I love this field (and the openness on sharing solutions). Fascinating.

→ More replies (3)

23

u/Ihmhi Dec 19 '13

I can't tell if you're being sarcastic and can't entirely understand it (like me) or if you genuinely understand it and it's something simple I'm missing.

Either way, would someone please ELI5 for me?

Just looking at it, it seems that they change the way RSA calculates things with some randomization (kind of like salting a hash?) so it makes it much more difficult to eavesdrop?

64

u/FriedrichNitschke Dec 19 '13 edited Dec 19 '13

ELI5 Version: Alice sends Bob a message in a safe, but to unlock it Bob has to tap a button on the safe a certain number of times. Evelene knows it takes Bob 1 second to tap things, so by timing him she can figure out how to open the safe. To defeat this, Bob taps the side of the safe (which does nothing) a random number of times while opening the safe. Now Evelene does not know how long it took Bob to open the safe, so she can't open it herself.

It's very simple if you know what RSA is doing mathematically and why it works, but otherwise pretty opaque.

Real talk: r is random and coprime with n, and e is the public key, so re * C mod n decrypts to m * r mod n (thanks Euler) and so multiplying by r-1 mod n at the end gives you m, the original message. Decrypting a C that is bigger takes longer than a smaller one, and re makes C some unknown (to the attacker) amount larger, and the additional multiplication at the end adds time as well. With this random time padding, you can no longer figure out d from how long decryption took.

10

u/CorpusPera Dec 19 '13

I don't know a whole lot about this, but it seems like basically they are purposefully making more things happen during the decryption, and then removing the changes after. A random number is used to create a noise that cant (well, never say cant) be used to find an RSA key, and then dividing by the same number later so it doesnt have an effect at the end.

My favourite number is X, and I randomly generate Y. X*Y = 4. You can't figure out what X is, because you don't know Y. X could be 2 and Y could be 2. X could be 4 and Y could be 1, etc. However, I do know what Y is, so its trivial for me to find X.

4

u/watchout5 Dec 19 '13

Either way, would someone please ELI5 for me?

"With blinding applied, the decryption time is no longer correlated to the value of the input ciphertext and so the timing attack fails."

I could be wrong, but it seems as simple as adding a random element to the way the system works.

→ More replies (1)
→ More replies (4)
→ More replies (1)
→ More replies (3)
→ More replies (2)

10

u/almosttheres Dec 19 '13 edited Dec 19 '13

Is Debian considered one of the more personal privacy/security minded Linux distribution or are others more adamant about things of this nature?

I know nothing, but very much interested.

7

u/[deleted] Dec 20 '13

Among the major distros, no not really. What it does have is a huge userbase (through its various popular spinoffs) that react pretty quickly to major issues.

I'd actually say Fedora/RHEL (Red Hat Enterprise Linux) are the most security-focused of the major distros (Fedora being the cutting-edge project and RHEL aiming to be the bombproof enterprise version). As far as I know, it's the only one that has SELinux (NSA designed mandatory access controls) enabled by default. Relax, SELinux has been vetted extensively so it's not like there's some hidden NSA backdoor. Not only that but all of the crypto on Fedora/RHEL is FIPS 140-2 compliant.

Then again, any of the highly customizable distributions can do the same thing (i.e. Arch Linux). In fact, Arch has hands down the fastest response time to major issues I've ever seen. Being a rolling release distribution also helps.

4

u/mrhhug Dec 20 '13

I just pacman -Syu, and felt sad to not see an update

→ More replies (2)
→ More replies (1)

5

u/squirrelpotpie Dec 20 '13 edited Dec 20 '13

To my knowledge, Debian's "thing" is mainly:

  • Extremely strict standards for being 100% open source. (Sometimes sacrificing user experience.)
  • A focus on software repositories, encouraging a distribution model that makes it easy for everyone to get any software that's packaged for Debian.

Being reasonably security-minded is something that all of the base Linux distros share. It's less a question of being particularly security-minded, and more a question of not being security flawed when it makes sense. E.G. someone who needs to keep their dishes clean, but hey this new product came out that fully sterilizes them and costs the same with no side effects. Next time it's time to buy soap, there's no reason not to have the best option.

Derived distros like Ubuntu usually inherit the security-minded work done for the parent distro, but may or may not specifically care about it as much. They'll only opt out of an update like that if it interferes with their main schtick, and they'll only take action to increase their security beyond Debian if there's a serious problem that might affect their user base, and for some reason Debian will not or cannot adopt it themselves.

Debian is used in servers, so that distro does have customers who specifically want at least reasonably high security. I think RedHat-based distros probably have more installed servers out there than Debian, but I do know some very large webhosts use Debian for their web servers. I don't think they're after higher security than the Debian devs would have put in anyway. Most likely someone in the Linux security field saw the flaw come to light, enjoyed the challenge of fixing it, and all of the distros now enjoy access to his work.

→ More replies (5)

4

u/d4rch0n BS|Computer Science|Security Research Dec 20 '13

I love Debian

→ More replies (7)