3 ms·

Why? The screenshot mentions RSA-2048. At which point of that algorithm is random input so important that it breaks the encryption if you don't have access to a

by onli 14y ago

Why? The screenshot mentions RSA-2048. At which point of that algorithm is random input so important that it breaks the encryption if you don't have access to a true random number generator? I know that you choose p and q by random. And it is obvious that you want to choose numbers that an attacker can't easily guess. But not having access to a hardware number generator doesn't automatically imply you have a real useable vulnerability here, or does it?

daeken 14y ago
Not generating good random numbers is not a huge concern for something like AES, where there's just such a large search space. But with RSA, generating a "bad prime" is the difference between something taking until the death of the sun to break, and taking days. Edit: To clarify, primes for RSA keys are generated probabilistically -- we don't really know that they're prime, we just have a fair amount of confidence to that effect. It's entirely possible to generate bad 'primes' that really aren't prime at all, which makes factoring the keys trivial.
- onli 14y ago
  Thanks for the answer. But I don't understand that. For generating the prime-numbers used, you basically guess a number and use the miller-rabin-test or something like that to test if prim. Maybe you have a better approach, but generally, that should be equally possible using JS as any other language. You never want to implement something like this yourself for a real product, of course, but i don't see that specific issue. They even could build upon something like jsbn[1] I thought that this is about a missing random number generator. [1]http://www-cs-students.stanford.edu/~tjw/jsbn/ http://www-cs-students.stanford.edu/~tjw/jsbn/
  - daeken 14y ago
    I am not a crytographer (by any means!), but my understanding from conversations with folks in that space is that it's very possible for a bad PRNG to generate primes that pass the standard tests but are still very breakable. I really don't have any more information than that; I should read up more there. Either way, that's by no means the biggest issue here -- some browsers already have CSPRNGs -- but rather that the code is coming from their server and is considered to be compromised by default. Browser-side crypto without very strict security boundaries on key generation and access is just bad news.
- tptacek 14y ago
  WAT? Bad random numbers are fatal to AES. Attacks against "AES" with a bad RNG don't attack the whole AES keyspace; they attack the bad RNG; in effect, implementing AES with a bad RNG reduces the security of the system to that of the RNG.
nwh 14y ago
RSA relies on large primes for the private/public key generation. The random functions in browsers aren't designed to make numbers like it, and are probably based on algorithms like the mersenne twister, which are fast but very predictable. So much so that based on a number of samples, the pseudo-random number generators in common languages can be guessed with very high accuracy. It's essentially bad because the generated secret keys are predicable, to the point where a single CPU could crack them in minutes, which is obviously undesirable.
- onli 14y ago
  I don't see how such an attack would be possible on a piece of software which does RSA-key-generation and is seeding the random-number-generator with input from the user. How would you get multiple samples? You wouldn't get any sample at all, apart from maybe the public-key (probably not even that). To do such an attack based on the pseudo-random-number-generator, someone on the outside of the key-generation-process would need to be able to guess the prime-numbers used on a specific account just by the predictability of the rng. How should that work? Again, if having the choice, I will always use the conservative option when dealing with crypto-stuff (using an approved crypto-library). And really: Not saying what you say is wrong. Just don't see the attack-vector here. Would you like to give me a hint?
  - nwh 14y ago
    I'm not entirely sure how the Mega entropy gathering system works, but I can take a guess. Through the sign up process try ask for users to both enter information with the keyboard, and click buttons with the mouse. There's not a whole lot of randomness in either action, and relying on it too much could start to reveal things about the user in the encryption key generated. For this, lets assume I can predict the random numbers with minimal computation. That's realistic. PHP session variables can have their random seed extracted in a very short time frame using similar methods (<30 minutes). They would first be relying on the randomness of the path that users take with their mouse between buttons. That's unfortunately fairly predictable, most of the users will click on the buttons in the same order, and probably take reasonably similar paths to get there. If we could work out the probabilities, the key search could be focused on the most likely path a user might take. So we move on to keystrokes. There's not a whole lot of variation there either. If we use the keystrokes themselves, we might begin to reveal personal information in the key. I'm sure you wouldn't want your password baked into the keys you are relying on to protect your freedom / anonymity. The length of keystroke is what they would use, how much time the button stays down and the distance in time between keystrokes. There's some randomness there, but I wager that most people type with the same sort of characteristics. If they're on a touch screen device like an iPhone, you get no real timing information except for delay between letters. There's no denying that it is still brute force and very unlikely, but using attacks like that could be the difference between decades of computation and hours
gizmo686 14y ago
An encryption algorithm can be no stronger than the random number generator that created the keys. Any weakness in that generator will allow an attack to improve his odds in a guess and check brute force attack.
- onli 14y ago
  That doesn't sound right in this absolutenes (it is of course not wrong). For example, given a rng that is attackable when being allowed to get multiple random values from it after the rng was seeded, i still see no attack on rsa in a scenario such as this, when the rng is only used to create the key (see [1]). You wouldn't get the necessary samples for the attack. I already agreed that sure, if you can guess the prime-numbers because of a flaw in a rng, that is a serious issue. But I don't see how it follows that if you use javascript for the key-creation it is guaranteed you will use a rng with predictable outcome, especially not if you use user-input like described in the screenshot. [1] http://blog.cryptographyengineering.com/2012/03/surviving-bad-rng.html http://blog.cryptographyengineering.com/2012/03/surviving-ba...
  - gizmo686 14y ago
    The problem is that a cryptographicly secure rng generates all numbers with equal probability. Non-cryptographic rng s have no such guarantee, so even given a truly random seed and a single value taken from the rng, one might still know something about the distribution of the rng's output that will allow them to know what values are more likely to have been produced, therefore allowing them to launch a brute force attack using the most likely values first, reducing the number of attempts they can expect to need in order to find the correct key. That is not to say that one cannot use javascript for secure key generation, however one must make sure that the algorithm used to convert the truly random entropy into a useful random number is secure.

by onli 14y ago

daeken 14y ago

Not generating good random numbers is not a huge concern for something like AES, where there's just such a large search space. But with RSA, generating a "bad prime" is the difference between something taking until the death of the sun to break, and taking days. Edit: To clarify, primes for RSA keys are generated probabilistically -- we don't really know that they're prime, we just have a fair amount of confidence to that effect. It's entirely possible to generate bad 'primes' that really aren't prime at all, which makes factoring the keys trivial.

onli 14y ago
Thanks for the answer. But I don't understand that. For generating the prime-numbers used, you basically guess a number and use the miller-rabin-test or something like that to test if prim. Maybe you have a better approach, but generally, that should be equally possible using JS as any other language. You never want to implement something like this yourself for a real product, of course, but i don't see that specific issue. They even could build upon something like jsbn[1] I thought that this is about a missing random number generator. [1]http://www-cs-students.stanford.edu/~tjw/jsbn/ http://www-cs-students.stanford.edu/~tjw/jsbn/
- daeken 14y ago
  I am not a crytographer (by any means!), but my understanding from conversations with folks in that space is that it's very possible for a bad PRNG to generate primes that pass the standard tests but are still very breakable. I really don't have any more information than that; I should read up more there. Either way, that's by no means the biggest issue here -- some browsers already have CSPRNGs -- but rather that the code is coming from their server and is considered to be compromised by default. Browser-side crypto without very strict security boundaries on key generation and access is just bad news.
tptacek 14y ago
WAT? Bad random numbers are fatal to AES. Attacks against "AES" with a bad RNG don't attack the whole AES keyspace; they attack the bad RNG; in effect, implementing AES with a bad RNG reduces the security of the system to that of the RNG.

nwh 14y ago

RSA relies on large primes for the private/public key generation. The random functions in browsers aren't designed to make numbers like it, and are probably based on algorithms like the mersenne twister, which are fast but very predictable. So much so that based on a number of samples, the pseudo-random number generators in common languages can be guessed with very high accuracy. It's essentially bad because the generated secret keys are predicable, to the point where a single CPU could crack them in minutes, which is obviously undesirable.

onli 14y ago
I don't see how such an attack would be possible on a piece of software which does RSA-key-generation and is seeding the random-number-generator with input from the user. How would you get multiple samples? You wouldn't get any sample at all, apart from maybe the public-key (probably not even that). To do such an attack based on the pseudo-random-number-generator, someone on the outside of the key-generation-process would need to be able to guess the prime-numbers used on a specific account just by the predictability of the rng. How should that work? Again, if having the choice, I will always use the conservative option when dealing with crypto-stuff (using an approved crypto-library). And really: Not saying what you say is wrong. Just don't see the attack-vector here. Would you like to give me a hint?
- nwh 14y ago
  I'm not entirely sure how the Mega entropy gathering system works, but I can take a guess. Through the sign up process try ask for users to both enter information with the keyboard, and click buttons with the mouse. There's not a whole lot of randomness in either action, and relying on it too much could start to reveal things about the user in the encryption key generated. For this, lets assume I can predict the random numbers with minimal computation. That's realistic. PHP session variables can have their random seed extracted in a very short time frame using similar methods (<30 minutes). They would first be relying on the randomness of the path that users take with their mouse between buttons. That's unfortunately fairly predictable, most of the users will click on the buttons in the same order, and probably take reasonably similar paths to get there. If we could work out the probabilities, the key search could be focused on the most likely path a user might take. So we move on to keystrokes. There's not a whole lot of variation there either. If we use the keystrokes themselves, we might begin to reveal personal information in the key. I'm sure you wouldn't want your password baked into the keys you are relying on to protect your freedom / anonymity. The length of keystroke is what they would use, how much time the button stays down and the distance in time between keystrokes. There's some randomness there, but I wager that most people type with the same sort of characteristics. If they're on a touch screen device like an iPhone, you get no real timing information except for delay between letters. There's no denying that it is still brute force and very unlikely, but using attacks like that could be the difference between decades of computation and hours

gizmo686 14y ago

An encryption algorithm can be no stronger than the random number generator that created the keys. Any weakness in that generator will allow an attack to improve his odds in a guess and check brute force attack.

onli 14y ago
That doesn't sound right in this absolutenes (it is of course not wrong). For example, given a rng that is attackable when being allowed to get multiple random values from it after the rng was seeded, i still see no attack on rsa in a scenario such as this, when the rng is only used to create the key (see [1]). You wouldn't get the necessary samples for the attack. I already agreed that sure, if you can guess the prime-numbers because of a flaw in a rng, that is a serious issue. But I don't see how it follows that if you use javascript for the key-creation it is guaranteed you will use a rng with predictable outcome, especially not if you use user-input like described in the screenshot. [1] http://blog.cryptographyengineering.com/2012/03/surviving-bad-rng.html http://blog.cryptographyengineering.com/2012/03/surviving-ba...
- gizmo686 14y ago
  The problem is that a cryptographicly secure rng generates all numbers with equal probability. Non-cryptographic rng s have no such guarantee, so even given a truly random seed and a single value taken from the rng, one might still know something about the distribution of the rng's output that will allow them to know what values are more likely to have been produced, therefore allowing them to launch a brute force attack using the most likely values first, reducing the number of attempts they can expect to need in order to find the correct key. That is not to say that one cannot use javascript for secure key generation, however one must make sure that the algorithm used to convert the truly random entropy into a useful random number is secure.