5

Why is 128bit AES considered very strong but 160bit SHA 'insufficiently secure'? Google/chrome/browsers seems to drop support for SHA1 SSL certificates. I assume it's more simple to calculate SHA than a round of AES but there are a lot more bits in SHA. I understand MD5 was depreciated bc the algorithm was broken enough that it was not difficult to create a collision but I don't think that comes into play with SHA?

  • 3
    @John. AES-128 is no joke: http://security.stackexchange.com/questions/61346/how-long-would-it-take-to-bruteforce-an-aes-128-protected-pdf-knowing-the-key-is – TTT Apr 29 '16 at 01:22
  • 5
    @John I would downvote your comment if I could. – Bacon Brad Apr 29 '16 at 03:26
  • 1
    There is nothing wrong with AES128. The best attack against AES is a biclique attack which can recover the key in 2^126.1 operations. That is far from "not strong". The only realistic attack against AES128 is an attack using grover's algorithm, which only runs on cryptoanalytic quantum computers, and we have no working ones capable of doing that yet. Those would reduce the effective keyspace of AES128 to 2^64, which is easier to search through. My point is, saying 128-bit encryption is a joke is bullshit. – forest Apr 29 '16 at 06:44
  • @John I think forest comment is for you –  Apr 29 '16 at 19:03
  • @forest: 2^64 sounds.... wrong. To be weaken that much you'd have to do `18,446,744,073,709,551,616` possibilities per attempt. I mean you'd need to divide 2^128 possibilities by 18446744073709551616(which is 2^64) to have it search only 2^64 space –  Apr 29 '16 at 22:33
  • 1
    Sure, it sounds wrong, but it isn't. Grover's algorithm reduces the keyspace of a symmetric cipher or hash by 2^(n/2). This means AES128 can be searched in 2^64 operations. It's a quantum algorithm, so it works in some really weird ways. It doesn't have to literally try `18,446,744,073,709,551,616` possibilities per attempt. According to Wikipedia, "Grover's algorithm could brute force a 128-bit symmetric cryptographic key in roughly 2^64 iterations, or a 256-bit key in roughly 2^128 iterations.". See https://en.wikipedia.org/wiki/Grover%27s_algorithm for more information. – forest Apr 30 '16 at 00:07

2 Answers2

11

For hash functions (like SHA-1) being used to sign SSL certificates, the security is completely undermined if you have successful collision attacks. Due to the birthday paradox, a N-bit hash function effectively provides about N/2 bits of security against collision attacks. That is a brute-forcer can create collisions for a N-bit hash function after generating about 2N/2 potential strings to hash. Hence an 160-bit hash function provides about 80-bits of security against collisions (meaning it takes about 280 effort to generate a collision via brute-force).

For a block cipher (like AES), you use a N-bit key that maps a block of text (128 bits in the case of AES) into a block of ciphertext in a reversible way if you possess the N-bit key. Hence, to brute force a block cipher with an N-bit key (and no other vulnerabilities), you need to try about 2N possible keys until you find a key that transforms the ciphertext into the original message.

Thus (without looking at any specific flaws in the two algorithms), a block cipher with a 128-bit key is much stronger (which takes 2128 effort to brute force) than using an SSL certificate signed with a 160-bit hash function (which takes 280 effort to find a collision and completely undermine the security). In fact it is roughly 248 ~ 281 trillion (1012) times more secure.

Explanation of why collisions break SSL certificates

Basically, an SSL certificate consists of some plaintext information p and a signature S provided by a certificate authority. This plaintext typically includes the name of your organization and your domain name and similar information. If you want a new certificate, you then submit this information to a certificate authority (CA) that popular web browsers intrinsically trust. The CA checks your information (e.g., they verify you own the domain, by say emailing a code to the email address listed in the DNS records for that domain, OR you pay for an extended validation certificate and the CA does more checks that you are the organization you say you are). If the information checks out, the certificate authority will agree to sign it and issue you the signature to complete the certificate. The signature consists of hashing the plaintext information H(p) in the certificate and then using the CA's private key (K_priv) to encrypt that hash (S = E(K_priv, H(p)). Then anyone can use the corresponding public key of the CA (K_public) (and your operating system and/or web browser typically comes with a list of public keys of trusted certificate authorities) to decrypt the signature to find H(p) = D(K_public, S) and verify that the signature matches the hash of the plaintext information in the SSL certificate.

Thus if you generate roughly 280 different plaintext messages p (some in the form needed to be a certificate for a domain, some in the form of certificates for intermediate certificate authority), it could be possible to find a pair of two messages p1 and p2 that collide. If say p1 identifies a randomly changed domain (sgnjnjrafaftjhyqsv.com) that you can easily buy (or you vary subdomains of domains you already own like sgnjnjrafaftjhyqsv.blah.com), then you can verify ownership of p1 to a CA and you can get a CA's signature of p1. Since the hashes match H(p1)==H(p2), you can take the signature from p1's certificate and use it with p2 to generate a valid certificate. If p2 for example was an intermediate certificate authority that allows you to sign other certificates, you could then use that intermediate certificate authority to sign any certificate you want (and could for example spoof any website you want -- at least ignoring other protections like certificate pinning).

For reference, this attack was successfully used to create fake intermediate certificate authorities against MD5 (128-bit hash) signed certificates around 2008. Note, ignoring specific flaws in the relevant hashes finding a SHA-1 collision is only about 65,000 times more difficult than finding one in an MD5 hash. With the cost of computation decreasing, it is believed to be feasible for sophisticated attackers to collision attack SHA-1 and undermine SSL security. Using a 256 bit hash (like SHA-256) is about 18 billion billion (18 x 1018) times more secure than a 128 bit hash (like MD5) against collision attacks (again ignoring specific flaws in the hash functions).

dr jimbob
  • 38,768
  • 8
  • 92
  • 161
  • Interesting but I am confused about the difference between security bits and nonsecure bits. We definitely get 20bytes of data when using SHA so security bits aren't hidden from us AFAIK. Why isn't all the bits security bits or what makes the nonsecure bits so weak? But now this sounds more of a collision attack rather than brute force attack –  Apr 29 '16 at 22:36
  • If you try to do a birthday attack, you don't actually need a random looking domain, instead of varying the domain, you can also vary the other certificate details that aren't as visible to the user, like the Organisation or Country name. – Lie Ryan Apr 30 '16 at 11:11
  • @LieRyan - Totally agree. If you look at the edit history the whole idea was introduced by an edit that someone else approved. (Originally I wrote "If say p1 was a certificate for a domain you own and can verify ownership to a CA, you can get a CA to sign it" but was changed to "If say p1 happens to identify any free domain (like phpsdfpspfopo.tv) that you can buy any minute, then you can verify ownership of p1 to a CA and you can get a CA's signature of p1." Granted, changing the domain/subdomain seems a pretty simple way to explain changing `p1` without going to fine details. – dr jimbob Apr 30 '16 at 18:57
  • @acidzombie24 - Yes, the security of accepting a particular hash function as part of a validly signing a certificate fundamentally relies on the infeasibility of collision attacks. There's no such thing as "nonsecure bits", it's just a 160 bit hash function takes roughly 2^80 effort to generate a collision to break. This is roughly comparable to the effort to brute-force a block cipher with an 80-bit key. – dr jimbob Apr 30 '16 at 19:02
  • Not to mention that there are attacks that makes it easier to find SHA-1 collisions under certain circumstances whereas such attempts on a block cipher like AES is pointless unless it completely breaks the cipher. – billc.cn May 03 '16 at 10:42
5

AES is a symmetric encryption algorithm. SHA-1 is a hashing function. They are completely different beasts.

The issue is not the number of bits but the functions themselves. As an example you can take MD5. It also has 128 bits, yet creating two colliding strings is now trivial.

The issue is not being able to bruteforce the 128-bit possibilities, but (ab)using the properties of the md5 operations for forcing the collision.

Ángel
  • 17,578
  • 3
  • 25
  • 60
  • 1
    I had to downvote this because it doesn't mention the primary reason collisions are easier. The fact is, for brute-force resistance for AES128, you have 2^128 bits. For collision resistance, you have half of the bit size, so for SHA-1, which is 160 bits, you only have 90 bits of collision resistance. For MD5, which is 128 bits, you have a mere 64 bits of collision resistance, which of course is very easy to break. – forest Apr 29 '16 at 05:56