9 ms·

Bicycle Attacks: Quantifying the Damage of Widespread Password Length Leakage

30 points by adulau 7y ago

unwind 7y ago
Not being into security much (if I can help it) I had to look up the term [1]. Basically it's a reference to how a (tightly) wrapped bike is still recognizable as being a bike. [1] https://en.m.wikipedia.org/wiki/Bicycle_attack https://en.m.wikipedia.org/wiki/Bicycle_attack
dmurray 7y ago
If you learn the exact length of a password, you gain say 3-4 bits of entropy? 4 bits if there are sixteen possible password lengths, all equally likely. 4 bits is not nothing, and it makes most cracking attacks 16 times easier, but it's hopefully never going to be the difference between good security and bad.
- deleted 7y ago
  [deleted]
- tyingq 7y ago
  "never going to be the difference between good security and bad." True, though there's plenty of bad out there. Combined with dumb password rules, knowing the exact length could make things pretty easy. Like the US Global Entry password rules: https://raw.githubusercontent.com/dumb-password-rules/dumb-password-rules/master/screenshots/global-entry.png https://raw.githubusercontent.com/dumb-password-rules/dumb-p... 8-12 chars with so many rules that already reduce the search space.
  - pintxo 7y ago
    They might as well just supply the list of allowed passwords /s
  - dmurray 7y ago
    I don't think those rules reduce the entropy significantly, maybe 1 bit compared to a rule of "any character on a US keyboard, max length 12". You can try generating a random password with that rule and see if it passes the test - more than half of the time it will. The problem with overly restrictive password rules is not generally a lack of entropy. It's that people can't remember their passwords, which might be a bug or a feature.
    - tyingq 7y ago
      I'd like the see the math on that 1 bit reduction. There's 3 "at least one char must be" and the first char must be 0-9a-Z. If the password is 8 characters, half of them, at least, have a much reduced search space.
      - dmurray 7y ago
        There are 100 million more 12-character passwords than 8-character ones, so if you randomly choose from all 8-12 character passwords, it's pretty close to just saying "choose a 12-character password". Let's say the alphabet is 93 characters (lower case, upper case, numbers, and the 31 special characters listed). So consider a random 8- to 12-character string in that alphabet. 1% of the strings have fewer than 12 characters. Lots of them will be legal, but let's eliminate them all to be conservative. 31/93 of the strings start with an illegal character, so that eliminates 33% of the strings. About 10 * 1/97 * 1/97 will have three consecutive occurrences of the same character. That eliminates another 0.1%. (83/93) to the power of 11 will have no numbers. That eliminates 28% of the remainder, or 18% of the total. By the same logic, 1% will have no special symbol. A negligible amount have no letter. One password in a million might contain the user's ID (supposing the IDs are 7-digit strings - either way, it will be negligible). Likewise there aren't many random passwords which will be the user's previous password or contain his name. That eliminated 53% of random passwords, leaving 47% for a loss of very close to one bit of entropy. This analysis wasn't completely rigorous as some of the requirements overlap, but if you try it through simulation I'm sure the result will be between 0.7 and 1.7 bits lost.
  - misnome 7y ago
    That looks saner than ours; The chosen password must: - Be at least 10 (ten) characters long (and must not be longer than 127 characters) - Contain at least 8 (eight) different characters, each of which is used only ONCE - Contain at least 2 letters (case sensitive) - Contain at least 2 numbers - Contain at least 2 of the symbols !”#$%&’()*+,-/:;<=>?@[\]^_`{}~¦ The chosen password must not: - Contain a £ (Pound) character - Have 3 of any repeating character next to each other - Spell a word of 4 letters or more listed in a common dictionary (Most 4 letter combinations) - Be an abbreviation associated with the company - Be based on your user name Unsurprisingly, almost everyone just memorises the initial random password given out, since it's provided on a nice piece of paper when you start. Thankfully there isn't also an expiry policy. The max length is large but that's basically meaningless when you actually need to remember it and it takes a while to come up with even a random password that fulfills these requirements.
    - BrandoElFollito 7y ago
      I work in information security for 25 years. This is the most surrealistic password policy I have seen. Fantastic awareness training material you have here (in the section "see, others have it worse than we do") A sad part is that it is virtually impossible to use a password manager to generate a new password.
  - medmunds 7y ago
    While there are still plenty of sites out there with absurd password requirements, I believe this particular example is outdated. When I used it last year, US Global Entry had changed over to the login.gov authentication service. The new rules are “It must be at least 12 characters long and not be a commonly used password. That’s it!” https://login.gov/assets/img/help/4-choose-a-password.png https://login.gov/assets/img/help/4-choose-a-password.png (Login.gov implements the relatively recent NIST 800-63 standard, which prohibits a lot of the earlier password absurdity.)
    - tyingq 7y ago
      Oh, that's good news.
- vbezhenar 7y ago
  If I don't know length, I need to start with length 1 and so on. If I know that password have 96 bits length, I'll skip lengths from 1 to 95. It's 2^1 + 2^2 + ... + 2^95 = 2^96 - 2 passwords. I still need to try 2^96 passwords at most. So I saved 1 bit.
- deleted 7y ago
  [deleted]
tyingq 7y ago
It feels like browsers could fix this in a fairly simple way. Something like using a value for the form boundary that varies in length for each request, or a X-RandPad type header that has some variable length data?
- madacol 7y ago
  I think there should be a protocol in browsers where input password fields are hashed along with a blinding factor that comes from servers. I think that protocol would solve lots of basic problems in password security. But the most important thing is that it would serve as a proof that the server is not saving your password in plain text, because the plain text never gets there, only it's hash.
  - MattPalmer1086 7y ago
    I can't see how this would work. Does the blinding factor change every time you log in? How does the server validate that your password is correct - what does it store? Server -> User : blinding factor User -> Server: H(password || blinding factor) Server: stores/checks what?
    - madacol 7y ago
      Server should save the blinding factor along with the hash. (Maybe some sort of global blinding factor could work, and generate it deterministically?) Server saves more data, but has the benefit that the rounds is computed in the client, so server's hash verification could be faster. (EDIT: To reduce rounds in server is probably not a good idea) I'm no nearly an expert in this stuff, so take it with a kilogram of salt.
    - usrusr 7y ago
      Server stores H(pw || bFixed) Server sends bFixed, bOnce Client sends H(H(pw || bFixed) || bOnce) The server can be trusted to not save the actual password if setup/change is already sending H(pw || bFixed) instead of the password itself. But then bFixed becomes public knowledge knowledge and a leaked H(pw || bFixed) would be enough to do a malicious login.
tialaramex 7y ago
It is surprising to me that modern browsers don't pad TLS (in TLS 1.3 padding is "free" in the sense that you don't need any extra bytes to say "this is padding") to fill the last packet. Supposing MSS is 1500 for a link, how much longer can it conceivably take to send say 1500 bytes including 120 bytes of padding versus 1380 bytes?
- toast0 7y ago
  Software layering makes this much harder than it should be, but it's a good concept. One potential pitfall is that an unfortunate number of networks still have poor path MTU detection, so padding that makes the packets larger than any previously sent packet in the stream may result in a packet too large to transit the network. Then you're at the mercy of ICMP delivery or path MTU blackhole detection, which tends to be slow and isn't enabled on Android (!).
  - tialaramex 7y ago
    Somewhere, one of the layers is picking a packet size. Probably the OS TCP stack. What I'd want to do as a TLS implementation concerned about hiding exact lengths is use that packet length for my final packet regardless of how much is actually inside it. Yes if the MTU is bogus and causes fragmentation or dropped packets that's bad, but I'm comfortable it also happened to every other packet sent, I'm only making things go from terrible to slightly more terrible, not from good to bad, and only for people who've got problems.
    - toast0 7y ago
      > Yes if the MTU is bogus and causes fragmentation or dropped packets that's bad, but I'm comfortable it also happened to every other packet sent, I'm only making things go from terrible to slightly more terrible, not from good to bad, and only for people who've got problems. Certainly, this would only affect people who have problems, which is low, but if you're always padding all requests up to the full MTU, it has the potential to make things go from almost always working, to never working. Looking at tcpdump with a real browser to one of my sites, firefox is only sending pretty short packets, everything is less than 512 bytes. But if you pad out to the full MTU, and the network is broken, those large packets may all be dropped, and the ICMPs either supressed filtered or so rate limited that they never get seen. Users on these networks with this padding would not be able to make https requests to most servers, but would be able to make connections to services where they have taken special effort to avoid MTU problems. Special efforts like: Google and Facebook clamp the maximum MSS they send to 1380 and 1400 for IPv4; FreeBSD used to return the client MSS in SYN+ACK if it was smaller than the locally configured MSS, but that was removed with this commit: https://github.com/freebsd/freebsd/commit/e1f9aeedee0bae92811248f9fcefa92ccb7be91f#diff-f3fd9f911dd76ffd9fbd0c8bfb458a61 https://github.com/freebsd/freebsd/commit/e1f9aeedee0bae9281...
blattimwind 7y ago
Bicycle attacks, because remembering that biclique attack is not spelled bicycle attack wasn't quite hard enough yet :-)
- SAI_Peregrinus 7y ago
  "Biclique" is pronounced "bye-kleek". I don't think "bicycle" usually sounds anything like that, so it shouldn't be too difficult.
rahuldottech 7y ago
Shouldn't you be able to avoid this by simply hashing the password before POSTing it?
- cestith 7y ago
  If you're using JS to prehash before submission, an attacker who has exfiltrated hashes never needs to crack them. It also makes it impossible to degrade gracefully for a non-JS client. You're effectively taking a password hash and turning it into an unhashed password itself.
- DGAP 7y ago
  Yes! But that has various pros and cons as well.

30 points by adulau 7y ago

Not being into security much (if I can help it) I had to look up the term [1]. Basically it's a reference to how a (tightly) wrapped bike is still recognizable as being a bike. [1] https://en.m.wikipedia.org/wiki/Bicycle_attack https://en.m.wikipedia.org/wiki/Bicycle_attack

dmurray 7y ago

If you learn the exact length of a password, you gain say 3-4 bits of entropy? 4 bits if there are sixteen possible password lengths, all equally likely. 4 bits is not nothing, and it makes most cracking attacks 16 times easier, but it's hopefully never going to be the difference between good security and bad.

deleted 7y ago
[deleted]
tyingq 7y ago
"never going to be the difference between good security and bad." True, though there's plenty of bad out there. Combined with dumb password rules, knowing the exact length could make things pretty easy. Like the US Global Entry password rules: https://raw.githubusercontent.com/dumb-password-rules/dumb-password-rules/master/screenshots/global-entry.png https://raw.githubusercontent.com/dumb-password-rules/dumb-p... 8-12 chars with so many rules that already reduce the search space.
- pintxo 7y ago
  They might as well just supply the list of allowed passwords /s
- dmurray 7y ago
  I don't think those rules reduce the entropy significantly, maybe 1 bit compared to a rule of "any character on a US keyboard, max length 12". You can try generating a random password with that rule and see if it passes the test - more than half of the time it will. The problem with overly restrictive password rules is not generally a lack of entropy. It's that people can't remember their passwords, which might be a bug or a feature.
  - tyingq 7y ago
    I'd like the see the math on that 1 bit reduction. There's 3 "at least one char must be" and the first char must be 0-9a-Z. If the password is 8 characters, half of them, at least, have a much reduced search space.
    - dmurray 7y ago
      There are 100 million more 12-character passwords than 8-character ones, so if you randomly choose from all 8-12 character passwords, it's pretty close to just saying "choose a 12-character password". Let's say the alphabet is 93 characters (lower case, upper case, numbers, and the 31 special characters listed). So consider a random 8- to 12-character string in that alphabet. 1% of the strings have fewer than 12 characters. Lots of them will be legal, but let's eliminate them all to be conservative. 31/93 of the strings start with an illegal character, so that eliminates 33% of the strings. About 10 * 1/97 * 1/97 will have three consecutive occurrences of the same character. That eliminates another 0.1%. (83/93) to the power of 11 will have no numbers. That eliminates 28% of the remainder, or 18% of the total. By the same logic, 1% will have no special symbol. A negligible amount have no letter. One password in a million might contain the user's ID (supposing the IDs are 7-digit strings - either way, it will be negligible). Likewise there aren't many random passwords which will be the user's previous password or contain his name. That eliminated 53% of random passwords, leaving 47% for a loss of very close to one bit of entropy. This analysis wasn't completely rigorous as some of the requirements overlap, but if you try it through simulation I'm sure the result will be between 0.7 and 1.7 bits lost.
- misnome 7y ago
  That looks saner than ours; The chosen password must: - Be at least 10 (ten) characters long (and must not be longer than 127 characters) - Contain at least 8 (eight) different characters, each of which is used only ONCE - Contain at least 2 letters (case sensitive) - Contain at least 2 numbers - Contain at least 2 of the symbols !”#$%&’()*+,-/:;<=>?@[\]^_`{}~¦ The chosen password must not: - Contain a £ (Pound) character - Have 3 of any repeating character next to each other - Spell a word of 4 letters or more listed in a common dictionary (Most 4 letter combinations) - Be an abbreviation associated with the company - Be based on your user name Unsurprisingly, almost everyone just memorises the initial random password given out, since it's provided on a nice piece of paper when you start. Thankfully there isn't also an expiry policy. The max length is large but that's basically meaningless when you actually need to remember it and it takes a while to come up with even a random password that fulfills these requirements.
  - BrandoElFollito 7y ago
    I work in information security for 25 years. This is the most surrealistic password policy I have seen. Fantastic awareness training material you have here (in the section "see, others have it worse than we do") A sad part is that it is virtually impossible to use a password manager to generate a new password.
- medmunds 7y ago
  While there are still plenty of sites out there with absurd password requirements, I believe this particular example is outdated. When I used it last year, US Global Entry had changed over to the login.gov authentication service. The new rules are “It must be at least 12 characters long and not be a commonly used password. That’s it!” https://login.gov/assets/img/help/4-choose-a-password.png https://login.gov/assets/img/help/4-choose-a-password.png (Login.gov implements the relatively recent NIST 800-63 standard, which prohibits a lot of the earlier password absurdity.)
  - tyingq 7y ago
    Oh, that's good news.
vbezhenar 7y ago
If I don't know length, I need to start with length 1 and so on. If I know that password have 96 bits length, I'll skip lengths from 1 to 95. It's 2^1 + 2^2 + ... + 2^95 = 2^96 - 2 passwords. I still need to try 2^96 passwords at most. So I saved 1 bit.
deleted 7y ago
[deleted]

tyingq 7y ago

It feels like browsers could fix this in a fairly simple way. Something like using a value for the form boundary that varies in length for each request, or a X-RandPad type header that has some variable length data?

madacol 7y ago
I think there should be a protocol in browsers where input password fields are hashed along with a blinding factor that comes from servers. I think that protocol would solve lots of basic problems in password security. But the most important thing is that it would serve as a proof that the server is not saving your password in plain text, because the plain text never gets there, only it's hash.
- MattPalmer1086 7y ago
  I can't see how this would work. Does the blinding factor change every time you log in? How does the server validate that your password is correct - what does it store? Server -> User : blinding factor User -> Server: H(password || blinding factor) Server: stores/checks what?
  - madacol 7y ago
    Server should save the blinding factor along with the hash. (Maybe some sort of global blinding factor could work, and generate it deterministically?) Server saves more data, but has the benefit that the rounds is computed in the client, so server's hash verification could be faster. (EDIT: To reduce rounds in server is probably not a good idea) I'm no nearly an expert in this stuff, so take it with a kilogram of salt.
  - usrusr 7y ago
    Server stores H(pw || bFixed) Server sends bFixed, bOnce Client sends H(H(pw || bFixed) || bOnce) The server can be trusted to not save the actual password if setup/change is already sending H(pw || bFixed) instead of the password itself. But then bFixed becomes public knowledge knowledge and a leaked H(pw || bFixed) would be enough to do a malicious login.

tialaramex 7y ago

It is surprising to me that modern browsers don't pad TLS (in TLS 1.3 padding is "free" in the sense that you don't need any extra bytes to say "this is padding") to fill the last packet. Supposing MSS is 1500 for a link, how much longer can it conceivably take to send say 1500 bytes including 120 bytes of padding versus 1380 bytes?

toast0 7y ago
Software layering makes this much harder than it should be, but it's a good concept. One potential pitfall is that an unfortunate number of networks still have poor path MTU detection, so padding that makes the packets larger than any previously sent packet in the stream may result in a packet too large to transit the network. Then you're at the mercy of ICMP delivery or path MTU blackhole detection, which tends to be slow and isn't enabled on Android (!).
- tialaramex 7y ago
  Somewhere, one of the layers is picking a packet size. Probably the OS TCP stack. What I'd want to do as a TLS implementation concerned about hiding exact lengths is use that packet length for my final packet regardless of how much is actually inside it. Yes if the MTU is bogus and causes fragmentation or dropped packets that's bad, but I'm comfortable it also happened to every other packet sent, I'm only making things go from terrible to slightly more terrible, not from good to bad, and only for people who've got problems.
  - toast0 7y ago
    > Yes if the MTU is bogus and causes fragmentation or dropped packets that's bad, but I'm comfortable it also happened to every other packet sent, I'm only making things go from terrible to slightly more terrible, not from good to bad, and only for people who've got problems. Certainly, this would only affect people who have problems, which is low, but if you're always padding all requests up to the full MTU, it has the potential to make things go from almost always working, to never working. Looking at tcpdump with a real browser to one of my sites, firefox is only sending pretty short packets, everything is less than 512 bytes. But if you pad out to the full MTU, and the network is broken, those large packets may all be dropped, and the ICMPs either supressed filtered or so rate limited that they never get seen. Users on these networks with this padding would not be able to make https requests to most servers, but would be able to make connections to services where they have taken special effort to avoid MTU problems. Special efforts like: Google and Facebook clamp the maximum MSS they send to 1380 and 1400 for IPv4; FreeBSD used to return the client MSS in SYN+ACK if it was smaller than the locally configured MSS, but that was removed with this commit: https://github.com/freebsd/freebsd/commit/e1f9aeedee0bae92811248f9fcefa92ccb7be91f#diff-f3fd9f911dd76ffd9fbd0c8bfb458a61 https://github.com/freebsd/freebsd/commit/e1f9aeedee0bae9281...

blattimwind 7y ago

Bicycle attacks, because remembering that biclique attack is not spelled bicycle attack wasn't quite hard enough yet :-)

SAI_Peregrinus 7y ago
"Biclique" is pronounced "bye-kleek". I don't think "bicycle" usually sounds anything like that, so it shouldn't be too difficult.

rahuldottech 7y ago

Shouldn't you be able to avoid this by simply hashing the password before POSTing it?

cestith 7y ago
If you're using JS to prehash before submission, an attacker who has exfiltrated hashes never needs to crack them. It also makes it impossible to degrade gracefully for a non-JS client. You're effectively taking a password hash and turning it into an unhashed password itself.
DGAP 7y ago
Yes! But that has various pros and cons as well.