5 ms·

My broker asks for 4-5 random letters of my password each time, making password managers unusable as well. Thinking about it now, how would you encrypt a passwo

My broker asks for 4-5 random letters of my password each time, making password managers unusable as well. Thinking about it now, how would you encrypt a password using this method? Create hashes of every combination?

chedabob 6y ago
Possibly using this? https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing I think a lot of implementations don't do anything clever and just have a fixed set of combinations they use each time, so the number of stored hashes is smaller.
- KMag 6y ago
  I thought about something similar to Shamir's Secret Sharing, polynomial fitting over a finite field, but in this case, information theory is working against you. With Shamir's Secret Sharing, you start out with your secret expressed as a finite field element, and pick N-1 polynomial coefficients uniformly randomly from your finite field, and give M different participants values of the polynomial evaluated at different points. Information theory shows that having at most N-1 points on the polynomial still leaks no information about F(0). It's as secure as a one-time pad, and in the degenerate case of N=2 over a Galois field, is in fact a XOR-based one-time-pad. The amount of entropy added at generation time is greater than the amount of entropy in the secret. In this partial password case, you'd want the "shared secret" to be a single value, and construct a polynomial such that, say 4 field elements, would always be sufficient to recover the same "secret". You're running the algorithm the wrong way, and unless you're forcing a password on the person, those letters are actually low-entropy instead of maximal entropy field points as in Shamir Secret Sharing. I really don't see a way to use polynomial interpolation in this way without leaking entropy. I thought about using something similar to Schnorr threshold signatures[0] to solve the information leakage, but then you end up storing one elliptic curve public key per password letter, and the private key for each public key is a single letter, so trivial to bruit-force. [0] https://eprint.iacr.org/2020/852.pdf https://eprint.iacr.org/2020/852.pdf
colejohnson66 6y ago
You can, but I’d assume they don’t. Plain text all the way! Ok, yes. Encryption could work, but encrypted passwords aren’t much better than plain text ones.
KMag 6y ago
Nit: I think you mean hashing, not encryption. Though, my bank uses a dual-password setup where the first password is required in its entirety and a few letters of the second password are required. I suspect this is stored by using a (hopefully memory-hard) salted key derivation function/password hash function (such as Argon2 or scrypt) to derive an encryption key from the first password, which is then used to decrypt the second password. At least, that's the way I'd design the system to minimize consequences of database compromise. Users are often not creative and often use related passwords. You'd want all of the stored information about the second password to provide clues to the first password only if the attacker had already cracked the first password. Hashing all of the permutations really blows up storage space and DB I/O.
- tinus_hn 6y ago
  Hashing in this sense is one way encryption.
  - KMag 6y ago
    Cryptographic literature often mentions one-way functions, but I don't think I've ever seen the phrase "one way encryption" in a cryptographic paper. It's not a phrase used by cryptographers, except rarely to describe encryption using trap door one-way functions such as RSA.
y7 6y ago
You wouldn't encrypt/hash it, since 4-5 letters (say 30 bits) is trivial to brute force anyway. Talking about offline password encryption/hashing is a bit of a red herring anyway, since it distracts from the fact that you're still sending your full password to the server for verification each time, so if the server is compromised for any length of time your password will be as well. Reusing passwords is broken: you really need different passwords for every service, and then it doesn't really matter whether the server stores them in plaintext. Asking for random letters is a poor man's version of a zero knowledge proof. It's only marginally more secure than asking for the full password (if you want to break into an account you need to observe someone entering the password a few times instead of just once), at the cost of a very crappy user experience.
- kevincox 6y ago
  A lot of these sites will even change the letters they ask for every time you reload the page. So the number of observations is probably less than 10. Maybe 1 if you have access to decent chunk of IPs (assuming they will block you if you reload the page too many times).
- jesboat 6y ago
  > you're still sending your full password to the server for verification each time, so if the server is compromised for any length of time your password will be as well. The key difference between storing plaintext passwords and hashed passwords is that with hashed passwords, you can only compromise users who log in during the interval when the system is compromised, and even then, only for worse compromises (eg if all the attacker gets is arbitrary disk read, compromising hashed passwords would be impossible in most scenarios.)
  - heavenlyblue 6y ago
    > users who log in during the interval when the system is compromised Why only then?
    - SAI_Peregrinus 6y ago

chedabob 6y ago

Possibly using this? https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing I think a lot of implementations don't do anything clever and just have a fixed set of combinations they use each time, so the number of stored hashes is smaller.

KMag 6y ago
I thought about something similar to Shamir's Secret Sharing, polynomial fitting over a finite field, but in this case, information theory is working against you. With Shamir's Secret Sharing, you start out with your secret expressed as a finite field element, and pick N-1 polynomial coefficients uniformly randomly from your finite field, and give M different participants values of the polynomial evaluated at different points. Information theory shows that having at most N-1 points on the polynomial still leaks no information about F(0). It's as secure as a one-time pad, and in the degenerate case of N=2 over a Galois field, is in fact a XOR-based one-time-pad. The amount of entropy added at generation time is greater than the amount of entropy in the secret. In this partial password case, you'd want the "shared secret" to be a single value, and construct a polynomial such that, say 4 field elements, would always be sufficient to recover the same "secret". You're running the algorithm the wrong way, and unless you're forcing a password on the person, those letters are actually low-entropy instead of maximal entropy field points as in Shamir Secret Sharing. I really don't see a way to use polynomial interpolation in this way without leaking entropy. I thought about using something similar to Schnorr threshold signatures[0] to solve the information leakage, but then you end up storing one elliptic curve public key per password letter, and the private key for each public key is a single letter, so trivial to bruit-force. [0] https://eprint.iacr.org/2020/852.pdf https://eprint.iacr.org/2020/852.pdf

colejohnson66 6y ago

You can, but I’d assume they don’t. Plain text all the way! Ok, yes. Encryption could work, but encrypted passwords aren’t much better than plain text ones.

KMag 6y ago

Nit: I think you mean hashing, not encryption. Though, my bank uses a dual-password setup where the first password is required in its entirety and a few letters of the second password are required. I suspect this is stored by using a (hopefully memory-hard) salted key derivation function/password hash function (such as Argon2 or scrypt) to derive an encryption key from the first password, which is then used to decrypt the second password. At least, that's the way I'd design the system to minimize consequences of database compromise. Users are often not creative and often use related passwords. You'd want all of the stored information about the second password to provide clues to the first password only if the attacker had already cracked the first password. Hashing all of the permutations really blows up storage space and DB I/O.

tinus_hn 6y ago
Hashing in this sense is one way encryption.
- KMag 6y ago
  Cryptographic literature often mentions one-way functions, but I don't think I've ever seen the phrase "one way encryption" in a cryptographic paper. It's not a phrase used by cryptographers, except rarely to describe encryption using trap door one-way functions such as RSA.

y7 6y ago

You wouldn't encrypt/hash it, since 4-5 letters (say 30 bits) is trivial to brute force anyway. Talking about offline password encryption/hashing is a bit of a red herring anyway, since it distracts from the fact that you're still sending your full password to the server for verification each time, so if the server is compromised for any length of time your password will be as well. Reusing passwords is broken: you really need different passwords for every service, and then it doesn't really matter whether the server stores them in plaintext. Asking for random letters is a poor man's version of a zero knowledge proof. It's only marginally more secure than asking for the full password (if you want to break into an account you need to observe someone entering the password a few times instead of just once), at the cost of a very crappy user experience.

kevincox 6y ago
A lot of these sites will even change the letters they ask for every time you reload the page. So the number of observations is probably less than 10. Maybe 1 if you have access to decent chunk of IPs (assuming they will block you if you reload the page too many times).
jesboat 6y ago
> you're still sending your full password to the server for verification each time, so if the server is compromised for any length of time your password will be as well. The key difference between storing plaintext passwords and hashed passwords is that with hashed passwords, you can only compromise users who log in during the interval when the system is compromised, and even then, only for worse compromises (eg if all the attacker gets is arbitrary disk read, compromising hashed passwords would be impossible in most scenarios.)
- heavenlyblue 6y ago
  > users who log in during the interval when the system is compromised Why only then?
  - SAI_Peregrinus 6y ago