6 ms·

Which means the password has much less entropy than it appears to have. It's a fun implementation, but not serious

by robbya 7y ago

tialaramex 7y ago
So, kinda, sorta, mostly no. We have these things called stream ciphers. You put a little bit of randomness in, and you get what seems to be lots of randomness out. For example the cipher might need a 256-bit key and 128-bit nonce and then spit out gigabytes of seemingly random data. Now, mathematically they can't /really/ be making more randomness, there's no random steps it's all deterministic, in principle it ought to be possible to unwind the steps and get back the initial random state. But it turns out that unwinding step just can't actually be done with a good stream cipher, that's the whole point. We do this sort of stuff a lot in real modern cryptography. There's a HN article which might still be on the front page, it was earlier today, explaining how SSH works. It shows that six keys are needed for SSH encryption, but they don't go get six times the randomness you'd need for a single key, they can just use a cryptographically strong hash function and make six different keys from the same shared secret randomness. Let's do an experiment: I've rolled my hex dice a few times to create a 64-bit random number. I've pushed that as ASCII text into MD5 and got back a result, and now I'm going to tell you the first and last characters of the result: F31FB042................81AFD8FA That's 64-bits. If you were correct with this idea about entropy you could tell me what the missing bits are, infact you could prove it to other posters - after all I have given you all the randomness according to your thinking, there can't be any left. But in fact you have no idea what those missing bits are, no idea what the original 64-bit number was, because you are wrong, with cryptographic primitives like hashes or stream ciphers we can in practice take a relatively small amount of entropy (like a few minutes of keyboard bashing by a toddler) and that's enough for all purposes. The _real_ reason you shouldn't use this to make passwords is that the site might be lying and keeping a record of every password that is chosen and which IP address it was given to etcetera.
- esotericn 7y ago
  This is not the case because one could enumerate the entire 64bit space and perform a rainbow table attack on your scheme.
  - jefftk 7y ago
    Simple brute force is not a rainbow table. Brute forcing 2^64 bits means calculating 2^63 MD5s in expectation. You can do ~100 GHash/sec, so ~2^37/s, so about 2^29s which is 17 gpu-years. So this is doable, but incredibly expensive.
    - thisacctforreal 7y ago
      Note that a it’s an entirely different story with a “real” kdf like scrypt or bcrypt. MD5 and SHA are specifically designed to be fast to compute, they shouldn’t be used for passphrases. Figured I’d bring it up in case there’s still PHP floating around with the once-typical practice of MySQL + MD5.
    - tialaramex 7y ago
      I'm glad my eyeballing the difficulty came off here. It was tempting to pick say 128-bits of randomness and SHA-512/256 where I'd stake actual money that it just cannot be done - but that's like twice as much die-rolling and typing. On the other hand if I do 32-bits (fewer rolls) and MD5 there's probably some loser out there who has already precomputed all of those for whatever reason and then somebody finds the answer with a Bing search and doesn't end up learning anything. echo -n 'F004672790DB5B1D' | md5sum f31fb042501c2a398974feca81afd8fa -
    - esotericn 7y ago
      Got me. I suppose I thought of 64bit as now being small. 48 would be doable.
- amarena 7y ago
  That is a PRNG, not a stream cipher.
  - Dylan16807 7y ago
    A secure PRNG and a stream cipher are pretty much the same thing. You take the random bits and XOR them with the stream, if you have one. The generation is the same.
preommr 7y ago
> It's a fun implementation, but not serious Well obviously, how was this business going to scale? Op can't keep making more kids in case the business really takes off.
dredmorbius 7y ago
Low-order bits from sufficient timing measurements would be effectively random. You're not looking at the characters, you're looking at the intervals between keypresses, and gathering the least significant digits of those. This is what PGP/GPG use for gathering entropy when generating keys as well. Not saying that's what's being done here, but it's a way to take fairly nonrandom activity and get decent entropy from it.
cpcallen 7y ago
Not necessarily. There's no way to know how much entropy is put in to the mix—it could be quite a lot.

Which means the password has much less entropy than it appears to have. It's a fun implementation, but not serious

by robbya 7y ago

Which means the password has much less entropy than it appears to have. It's a fun implementation, but not serious

So, kinda, sorta, mostly no. We have these things called stream ciphers. You put a little bit of randomness in, and you get what seems to be lots of randomness out. For example the cipher might need a 256-bit key and 128-bit nonce and then spit out gigabytes of seemingly random data. Now, mathematically they can't /really/ be making more randomness, there's no random steps it's all deterministic, in principle it ought to be possible to unwind the steps and get back the initial random state. But it turns out that unwinding step just can't actually be done with a good stream cipher, that's the whole point. We do this sort of stuff a lot in real modern cryptography. There's a HN article which might still be on the front page, it was earlier today, explaining how SSH works. It shows that six keys are needed for SSH encryption, but they don't go get six times the randomness you'd need for a single key, they can just use a cryptographically strong hash function and make six different keys from the same shared secret randomness. Let's do an experiment: I've rolled my hex dice a few times to create a 64-bit random number. I've pushed that as ASCII text into MD5 and got back a result, and now I'm going to tell you the first and last characters of the result: F31FB042................81AFD8FA That's 64-bits. If you were correct with this idea about entropy you could tell me what the missing bits are, infact you could prove it to other posters - after all I have given you all the randomness according to your thinking, there can't be any left. But in fact you have no idea what those missing bits are, no idea what the original 64-bit number was, because you are wrong, with cryptographic primitives like hashes or stream ciphers we can in practice take a relatively small amount of entropy (like a few minutes of keyboard bashing by a toddler) and that's enough for all purposes. The _real_ reason you shouldn't use this to make passwords is that the site might be lying and keeping a record of every password that is chosen and which IP address it was given to etcetera.

esotericn 7y ago
This is not the case because one could enumerate the entire 64bit space and perform a rainbow table attack on your scheme.
- jefftk 7y ago
  Simple brute force is not a rainbow table. Brute forcing 2^64 bits means calculating 2^63 MD5s in expectation. You can do ~100 GHash/sec, so ~2^37/s, so about 2^29s which is 17 gpu-years. So this is doable, but incredibly expensive.
  - thisacctforreal 7y ago
    Note that a it’s an entirely different story with a “real” kdf like scrypt or bcrypt. MD5 and SHA are specifically designed to be fast to compute, they shouldn’t be used for passphrases. Figured I’d bring it up in case there’s still PHP floating around with the once-typical practice of MySQL + MD5.
  - tialaramex 7y ago
    I'm glad my eyeballing the difficulty came off here. It was tempting to pick say 128-bits of randomness and SHA-512/256 where I'd stake actual money that it just cannot be done - but that's like twice as much die-rolling and typing. On the other hand if I do 32-bits (fewer rolls) and MD5 there's probably some loser out there who has already precomputed all of those for whatever reason and then somebody finds the answer with a Bing search and doesn't end up learning anything. echo -n 'F004672790DB5B1D' | md5sum f31fb042501c2a398974feca81afd8fa -
  - esotericn 7y ago
    Got me. I suppose I thought of 64bit as now being small. 48 would be doable.
amarena 7y ago
That is a PRNG, not a stream cipher.
- Dylan16807 7y ago
  A secure PRNG and a stream cipher are pretty much the same thing. You take the random bits and XOR them with the stream, if you have one. The generation is the same.

preommr 7y ago

> It's a fun implementation, but not serious Well obviously, how was this business going to scale? Op can't keep making more kids in case the business really takes off.

dredmorbius 7y ago

Low-order bits from sufficient timing measurements would be effectively random. You're not looking at the characters, you're looking at the intervals between keypresses, and gathering the least significant digits of those. This is what PGP/GPG use for gathering entropy when generating keys as well. Not saying that's what's being done here, but it's a way to take fairly nonrandom activity and get decent entropy from it.

cpcallen 7y ago

Not necessarily. There's no way to know how much entropy is put in to the mix—it could be quite a lot.