Bicycle Attacks: Quantifying the Damage of Widespread Password Length Leakage | Hacker News Reader

Bicycle Attacks: Quantifying the Damage of Widespread Password Length Leakage

arxiv.org

30 pointsadulau50 comments

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

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.

"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-p...

8-12 chars with so many rules that already reduce the search space.

They might as well just supply the list of allowed passwords /s

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.

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.

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.

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.

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.

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

(Login.gov implements the relatively recent NIST 800-63 standard, which prohibits a lot of the earlier password absurdity.)

Oh, that's good news.

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.

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?

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 (!).

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.

> 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/e1f9aeedee0bae9281...

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?

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.

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?

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.

  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.

That's Interesting!. I didn't thought it that way

What I had in mind is this:

  Server stores H(H(pw || bFixedPub) || bFixedPriv) , bFixedPub , bFixedPriv
  Server sends bFixedPub
  Client sends H(pw || bFixedPub)

bFixedPub and bFixedPriv are unique per password.

From the point of view of the server, the password is H(password || blinding factor)

So treat it like a password, salt it, do X rounds, and stores/checks result

Indeed, from the point of view of everybody (except the user), the password is H(password || blinding factor).

If I intercept H(password || blinding factor) and send it to the server (hashed with any other single use blinding factor), it will be accepted, even though I never knew the original password used to derive it.

So, this doesn't really achieve the goal that the server never stores your password in plain text, since the "plain text" of the password is exactly H(password||blinding factor).

It does mean the server may not know the original text you typed in to derive this password - but this is not needed to log in to the server.

Sure, it does not help in strengthening this particular server's authentication mechanism.

But it does serves as a proof for the user, that no matter however the server is storing the password, it won't be linkable to other's server way of storing the password, in case of reusing passwords.

And no matter how bad practice reusing a password is, people still do that, and I don't forsee a solution to that in the near future

> But it does serves as a proof for the user, that no matter however the server is storing the password, it won't be linkable to other's server way of storing the password, in case of reusing passwords.

Oh but there is, you can just try logging in with it (either for real or by running the login protocol on a dump/leak).

> Oh but there is, you can just try logging in with it (either for real or by running the login protocol on a dump/leak).

Sure, but that leak must have been from the same source.

Imagine you are a password-reuser, and you have registered with the same password in www.nottrustworthypage.com and www.yetanothernottrustworthypage.com

If they are using a would-be browser's built-in password protocol (which doesn't exist today, but this is what I'm suggesting and I sketched it in this comment https://news.ycombinator.com/item?id=22257502), and you know that if they are not colliding by using the same salt, and as long as your password is strong so it's not easily crackable, then you can have a pretty high confidence that whichever gets leaked, is very unlikely to damage your others site security.

Colliding salts require lots of efforts by the servers, and most of the damages produced by leaks, are because of lazyness

Imagine you are a password-reuser and you have registered with www.md5passwords.com and now BadPeople have cracked your password using a dictionary, BadPeople can now log into www.nottrustworthypage.com and www.yetanothernottrustworthypage.com.

The problem of your site's password best practice handling is that it does nothing to harden your users against other site's bad password handling. Hence FIDO.

It only proves that the server isn't storing your original password (since it never receives it). Well designed servers using salts and good password hashing don't do this anyway (but there are plenty of bad ones out there).

It doesn't prove that the server isn't just storing the derived password in plain text (which is all that is needed to log in to this server).

And it still doesn't mean that the original password can't be recovered if the password db is compromised.

@MattPalmer1086

Totally agree on the first 2 points

> And it still doesn't mean that the original password can't be recovered if the password db is compromised.

Why is that?

@madacol >> And it still doesn't mean that the original password can't be recovered if the password db is compromised.

> Why is that?

Because if I have the password db and the blinding value, I can just run a password cracker like hashcat over it to recover the original password with a reasonable probability.

Modern password cracking rigs with multiple GPUs can try out billions of hashes a second. If you know the salt or blinding factor, you can often recover the password.

> Modern password cracking rigs with multiple GPUs can try out billions of hashes a second. If you know the salt or blinding factor, you can often recover the password.

Isn't that what the rounds protects from?

You mean doing multiple rounds of hashing, like PBKDF2? There are some better algorithms than that now, but yeah, trying to slow down the computation required to crack the password is a useful defence.

Yeah, any way of increasing the cost factor, whether is PBKDF2 rounds, salt rounds in bcrypt, or just a pepper

The thing is, if the server is already doing all that good stuff with your password, then you're already as well protected as you can be with the current methods.

If it's not, then it probably won't be implementing your protocol either!

I agree that the current methods could be massively improved.

In the supposed scenario that the server sucks, and it stores directly whatever you sent them, no rounds, no salt, nothing, what you are left with, is whatever protection you did on the client side, so I'm thinking doing the rounds client-side.

Now that I'm thinking about it, I don't know how practical it is to do the rounds on a low-spec device like a cheap android

There are well worked out schemes which do achieve this e.g. Password Authenticated Key Exchange schemes (PAKE):

https://blog.cryptographyengineering.com/2018/10/19/lets-tal...

I'm pretty sure there are lots more, that probably are even better

But what I'm suggesting is that whatever it is, it should be integrated with the browser's, so that when I am typing my password in a special password-input-field (which doesn't exist today), no javascript is allowed to read it's plain text, until the user manually unlocks it and the page is able to read it's H(pw || bFixedPub) or whatever protocol is apropiate.

That special password field, should appear outside the pageview, to prove that the page is not in control of it, or it's not allowed to phish it, only the browser has control, and when it's done, it sends to the page the resulting hash

I do like the idea of password fields in browsers which can't be interrogated by javascript, a secure password protocol built in, and some way of making the authentication interface non spoofable.

In the comments section of that link, I found interesting this thread that touches what I am suggesting: https://blog.cryptographyengineering.com/2018/10/19/lets-tal...

Which ends up with one of the parties writing this: https://palant.de/2018/10/25/should-your-next-web-based-logi...

The blog in the last link argues against the usefulness with the built-in browser implementation.

The arguments are pretty useful, even though I disagree with he's conclusions. I think the fact that if a compromised server has to revert from the secure browser-built-in password form, to a "regular login form" in order to learn your password, then that's a win for me

Are you guys reinventing HTTP Digest auth here?

Yep!

There already are perfectly good algorithms for this stuff. What you want is an asymmetrical PAKE. The most notorious is SRP.

Don't try to roll your own. But basically there's no appetite at this point to retrofit SRP or any PAKE to "normal" user login on the web.

Avoid passwords altogether. If you must have passwords, have the very fewest possible (Buying more than one "single sign on" solution ought to be automatic grounds for firing the head of IT at a firm) and focus effort on getting rid of them not on trying to have better ones.

I explained more specifically what I am suggesting here. https://news.ycombinator.com/item?id=22257502

> Avoid passwords altogether...

I understand your point of view and you are right, securing passwords is hard.

I only see not-using-passwords feasible using hardware keys like yubikeys, which still might need a master password, but I don't see it becoming mainstream anytime soon

Yeah, this one seems like the simplest answer.

    the redundancy of the plaintext HTTP headers included in each and every request can be exploited in order to reveal the length of particular components

... so randomly change the HTTP header length by adding random sometimes-compressible data. X-whatever, or just change the ordering of header lines, or add randomness to the UA string.

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

Yes! But that has various pros and cons as well.

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.

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

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

Reply on news.ycombinator.com