H.323 Registration Weaknesses: Part 2

Last time, we have seen how Avaya's H.323 default gateway authentication method was vulnerable to an attacker that is able to passively intercept communications between a client and the gateway. Upon hearing this, we were pointed to the secure authentication method employed in Avaya's gear, with the proprietary OID 2.16.840.1.114187.1.6.2.

This new authentication method is based on DH-EKE, a password-based authenticated key exchange (PAKE). Invented by Bellovin and Merritt in the early 1990s, PAKE schemes kill two birds with one stone:

• They prevent dictionary attacks to recover passwords, even if an attacker is able to view all traffic;
• They prevent man-in-the-middle attacks if an active attacker does not know the password. This is an improvement over regular Diffie-Hellman key agreement.

Avaya's PAKE scheme is DH-EKE, One of the variants proposed originally by Bellovin and Merritt. Many more PAKE schemes have popped up over the years, like SPEKE, SRP, J-PAKE, or SPAKE2. Many of them are hindered by patents; EKE has the advantage of its patent having expired a few years ago.

In the secure scheme, the following message sequence happens between the gateway (\(G\)) and user (\(U\)):

• gatekeeperRequest (\(U \rightarrow G\)): \(U\) generates their own Diffie-Hellman public key, \(\text{DH}_U\), and encrypts it using AES-128 in CTR mode using a key derived from the first 16 bytes of SHA-1(password). \(U\) sends this encrypted public key to \(G\), along with a nonce \(R_e\), and \(IV\), the CTR mode nonce.
• gatekeeperConfirm (\(G \rightarrow U\)): \(G\) generates its own Diffie-Hellman key \(\text {DH}_G\) and computes the shared key \(K_m\) after decrypting \(U\)'s public key. \(G\) then sends back \(\text{DH}_G\) (unencrypted), a nonce \(R_g\), and the HMAC-SHA1-96 authenticator of this message (with a key derived from \(K_m\)).
• registrationRequest (\(U \rightarrow G\)): This request proceeds without any significant cryptographic material, except that an HMAC-SHA1-96 authenticator is appended to ensure that \(U\) also knows the shared key \(K_m\).
• registrationConfirm/registrationRejected (\(G \rightarrow U\)): This message notifies the client whether the registration failed or succeeded.

A good implementation of this protocol makes both offline password bruteforcing and man-in-the-middle attacks unfeasible, as pointed out above. When we analyzed Avaya's client software, however, we found the following optimization: the client did not generate a new Diffie-Hellman key for each registration. Instead, it caches the same \(\text{DH}_U\) for every registration within the same session. This allows offline bruteforcing of the password, which can also lead to man-in-the-middle attacks. 

How does this work? Suppose that an attacker captures two message exchanges like the above for the same user and password. Let \(\text{AES-CTR}_{K_p}(IV)\) be the keystream obtained by encrypting \(\text{IV}, \text{IV}+1\), etc, using \(K_p\) = SHA1(password)[0:16]. Since \(\text{DH}_U\) is the same for both exchanges, the encrypted content of the two gatekeeperRequest packets can be represented as follows:

\[ C_0 = \text{AES-CTR}_{K_p}(\text{IV}_0) \oplus \text{DH}_U \\ C_1 = \text{AES-CTR}_{K_p}(\text{IV}_1) \oplus \text{DH}_U \]

We can use this fact to test whether a guessed password is correct. Suppose we guess a password p; then it is the correct password only if 

\[ \text{AES-CTR}_{K_p}(\text{IV}_0) \oplus C_0 = \text{AES-CTR}_{K_p}(\text{IV}_1)  \oplus C_1 \]

Therefore one password check requires only two AES encryptions and one SHA-1 evaluation, and can be made extremely fast. GPU crackers could have a field day with this.

Unlike the case in the previous post, a sufficiently strong password is enough to thwart bruteforce, since this scheme is using stronger cryptographic primitives. But it is a safe assumption that most passwords are weak, especially so in phones, where it is more likely than not simple a PIN number.

I should also stress that this bug has been fixed; Avaya's PSST was rather forthcoming and professional in the handling of our report, and made the necessary steps to resolve this issue as quickly as possible.

H.323 Registration Weaknesses: Part 1

Voice-over-IP VoIP is a rather obscure niche. There are essentially two main standards: SIP and H.323. While the former may be more well-known by the Internet crowd, H.323 is still the dominant standard today for large deployments, due to the telecom heritage of ITU-T standards.

Some time ago, we found a vulnerability in the endpoint registration phase of several Avaya products. In fact, we found two vulnerabilities: one in the "default" autentication method for Avaya phones, and another one in the "secure" method. This post describes the first one. I will describe the second, more interesting, flaw in the next post.

The default authentication mode for Avaya's phones was based on the ISO/IEC 9798-2 standard. This is essentially a challenge-response protocol, wherein the user must prove to the gateway he knows the password by encrypting a gateway-chosen secret with a key derived from it. When a client wants to authenticate itself to a gateway, both knowing a shared secret (e.g., a password), the following interaction happens between the user (U) and the gatekeeper (G):

• gatekeeperRequest (\(U \rightarrow G\)): this message contains the authenticationCapability field set to pwdSymEnc, and the algorithmOIDs field set to the OID 1.3.14.3.2.6, which is defined to be DES in CTS mode.
• gatekeeperConfirm (\(G \rightarrow U\)): \(G\) sends back to \(U\) a ClearToken containing the challenge. This challenge consists of a timestamp, a random integer, and generalID, an identifier of the gateway.
• registrationRequest \(U \rightarrow G\): \(U\) sends the ClearToken back to \(G\), encrypted using the user's key \(K_{p}\) using the aforementioned DES-ECB-CTS. The key derivation is virtually nonexistent, and resembles the weak Norton Diskreet function breakable with Copacobana:



 unsigned char deskey[8] = {0,0,0,0,0,0,0,0};  
 for(i=0; i < pwlen; ++i)  
   deskey[i%8] ^= 2*password[i];  

• registrationConfirm/registrationRejected \(G \rightarrow U\): Depending on whether the authentication succeeded, the gateway will send back one of these messages to the user.

So what is the problem here? The protocol employed for the authentication, ISO/IEC 9798-2 (Mechanism 2), seems to be sound, according to its requirements. This protocol, however, does not do anything to prevent offline attacks that retrieve the shared key; since this key is derived from a (potentialy weak) password, bruteforce will work quite effectively.

One might argue that this is not really a weakness, and that a strong password should be able to keep attackers at bay. Unfortunately, due to the poor cipher choice (56-bit DES in ECB-CTS mode), poor key derivation function, and known plaintext (generalID), one is able to bruteforce any password, regardless of its strength.

Consider the following gatekeeperRequest sample packet:

0000   45 00 01 00 c0 17 24 09 12 02 6a df 14 00 44 00  E.....$...j...D.

0010   45 00 46 00 49 00 4e 00 49 00 54 00 59 00 2d 00  E.F.I.N.I.T.Y.-.

0020   47 00 4b                                         G.K             

We have known plaintext there, namely the UTF-16 string "DEFINITY-GK". Given the encrypted registrationRequest packet,

0000   3d 7a d2 d5 98 9a 04 1c 07 b0 b2 c0 ca 9b fb cb  =z..............

0010   c6 ab 9c 5a 74 e5 0f 4d 80 3e bf fe bb bb d9 ca  ...Zt..M.>......

0020   1d 33 ef                                         .3.             

we can obviously bruteforce the DES key out of a network capture. In this example, the password exployed was "3002".

DES bruteforcing is a very well studied problem, and specialized hardware can break any key quickly and at relatively low cost. With a weak key derivation as the above, it becomes much easier. Consider, for example, a long password that only uses the alphabet A-Z. This highly restricts the bit pattern to 010XXXXX, or 5 useful bits per byte, or \(2^{40}\) distinct keys, already smaller a keyspace than bruteforcing a 9-character password (\(\approx 2^{42}\) possibilities).

One can go even further, by noticing that similar products use similar generalID strings. This allows for precomputing to break those: using time-memory tradeoff techniques, an attacker can perform a single large precomputation that allows for  much faster key recovery. Martin Hellman showed that a precomputed table of \(2^{38}\) values allows for a recovery of the key in about \(2^{38}\) iterations, following a \(2^{56}\)-iteration table generation procedure. The state of the art today is rainbow tables, which provide a significant, albeit non-asymptotic, speedup over Hellman's method.

This is it for the old default authentication method. In short, the symmetric authentication method allows for offline password recovery, and to make it even worse, there is no password strong enough to withstand it. In the next post, we will see their public-key solution to the offline cracking problem, and how it was also broken.

Codegate YUT Preliminary 2013: bin500

Last weekend, we had the chance to play at the Codegate YUT 2013 preliminary match. The final challenge was in the binary category, and presented us with the following window:

This is a Win32 application that asks as input 6 lotto digits (from the set 0-9a-z), which are processed once you click the "BUY" button. 

The first hurdle to jump through is the anti-debugging and anti-disassembly. There is one thread, running at 0x00401C80, that continuously checks for changes in the main function of the application, such as breakpoints and patches. We disable this thread. There are also some sequences of code sprinkled around that confuse disassemblers:

.text:00402607    push    33h
.text:00402609    call    $+5
.text:0040260E    add     dword ptr [esp], 5
.text:00402612    retf
.text:00402613    call    $+5
.text:00402618    mov     dword ptr [esp+4], 23h
.text:00402620    add     dword ptr [esp], 0Dh
.text:00402624    retf

This is a known trick to jump between x86 and x86_64 mode under WOW64, and back again. Since no code is actually running in 64-bit mode, we can just safely nop out all those sequences and be done with it.

We are now ready to take a look at the main function, starting at 0x004046C0. The function first checks the lotto sequence for a hardcoded correct value, by checking the MD5 of each individual character. It is easy to figure out which character sequence results in the desired lotto: 58p1gt.

Once we get past this check, we see another check. This one matches the lower 8 characters of a modified SHA-1 of each lotto number to the hardcoded string 26c113b16b376f27f86192b1b6c0273aeae2066af4eb6dbb. We simply patch over this check, since the SHA-1 modification used here calls GetTickCount in its compression function; clearly it's meant to be random and to distract us.

 We finally reach the important part. The 6 lotto letters are xored with the string (at 0x0058D6AC) {0x15, 0x59, 0x1c, 0x48, 0x49, 0x6c}, and a 24-byte array is formed:

    unsigned char key[24] = 
    {
        '5', '8', 'p', '1', 'g', 't',
        '5'^0x15, '8'^0x59, 'p'^0x1c, '1'^0x48, 'g'^0x49, 't'^0x6c,
        '5', '8', 'p', '1', 'g', 't',
        'f', '3', 'v', '1', '4', '\0'
    };

This array is then used as the key to decrypt the hardcoded 24-byte block at 0x005B2814. The cipher used here is 192-bit block Rijndael. Not AES, Rijndael — AES is only defined for 128-bit blocks.

The winning key 58p1gt does not give out a meaningful decryption of the hardcoded block. What are we to do? Bruteforce! 6 characters from the allowed 0-9a-z 36-char dictionary means we only have to go through at most ~2^32 combinations. 

We quickly find that the correct lotto key to correctly decrypt the block is 4z9na3, and the flag is "L0tto_1s_noT_bAd_9ame!"

The bruteforcer used to get at the solution is available here.

Cloud hashing

Hash functions are everywhere. Getting this webpage to your computer has required at least a handful of hash calculations. We use them for identification, authentication, or even data structures, such as hash tables or Bloom filters. A particular strain of hash functions, cryptographic hash functions, tends to have more narrow uses: authentication (e.g., as part of HMAC), pseudorandom number generation, password storage (e.g., as part of HMAC in PBKDF2), and so on.

Until a few years ago, everyone was happy: MD5 ruled the land, while SHA-1 sometimes made an appearance. Disaster struck in 2004, when Xiaoyun Wang successfully found collisions in MD5, and seriously damaged SHA-1's reputation. Today, the landscape is different: MD5 and SHA-1 are no longer recommended, and SHA-2 and SHA-3 are the appointed replacements.

Yet, SHA-2 and SHA-3 do not fulfill every hash function requirement adequately. In particular, they are fairly slow in software, clocking at between 10 and 20 clocks per byte on modern x86 processors. In comparison, MD5 and SHA-1 clock between 4 and 6 clocks per byte. Applications that need to hash massive amounts of data will notice this gap. Therefore, such applications will often make the conscious choice to use SHA-1 or MD5, because a potentially insecure product is often better than an unresponsive product.

There are other options to consider when fast hashing (and non-strict adherence to standards) is required. Several SHA-3 finalists were very fast in software, such as BLAKE or Skein. Both are in the same order of magnitude of speed as MD5, and have passed the exhaustive level of scrutiny needed to get to SHA-3 finalist.

The recently announced BLAKE2 function takes advantage of the analysis already done on BLAKE, and strips the design of any unnecessary computational overhead. This results on a function that is expected to be as secure as SHA-3 in every way, but actually faster than MD5. Furthermore, BLAKE2 adds support for tree (parallel) hashing, which is a godsend for big data applications where sequential hashing would be simply too slow regardless of how optimized the design got.

So what are the applications of fast (and/or parallel) hashing?

File blacklisting/whitelisting is an obvious one; matching files to known hash sets is only dependent on disk and hashing speed. Fast-enough hashing can also benefit advanced filesystems. A remarkable case is ZFS, where a strong hash is supported (SHA-256), but disabled by default for performance reasons. SHA-256 is also required for other advanced features, such as deduplication.

Ultimately, pretty much every current hash use case does benefit from a faster function: faster equals less power consumed, and less overhead for the actual application. One exception is password storage, but you should not be using a plain hash function for that anyway!

SHA-3 has landed

Exactly 12 years after announcing Rijndael as AES, NIST has done it again. Keccak has been hailed as the SHA-3 winner. Congratulations to the Keccak team, who have designed an amazingly elegant hash, and in particular to Joan Daemen, who has now won 2 NIST competitions!

SHA-3 originated amidst fears that SHA-2, the current NIST hashing standard, was wounded after the breakthrough Wang attacks on MD4, MD5, and SHA-1. Furthermore, SHA-2, like its predecessors, suffered from the common flaws of the Merkle-Damgård (MD) construction, among which are length-extension attacks, faster-than-theoretical preimages and multicollisions. All SHA-3 finalists fixed these flaws, as a submission requirement.

The winner, Keccak, strays quite drastically from the SHA-2 design. Keccak uses the sponge construction, which relies on a fixed-width permutation \(f\) as the main building block, unlike the more common compression function from the MD designs. The sponge works in two phases: absorption and squeezing. Here's a picture:

The sponge construction

During the absorption phase, \(r\) bits from the message are injected into the state, after which the whole state (\(r+c\) bits) is permuted using \(f\). Once we're done with all the message bits (plus padding), we simply output the first l bits of the state as the final hash, applying the permutation repeatedly if necessary.

The strength of the sponge construction comes from the indifferentiability of f from a random permutation. Keccak is not perfect in this regard: an observation by Duan and Lai distinguishes the full Keccak permutation from random in expected \(2^{1579}\) time, down from \(2^{1599}\)  — not a real attack.

Performance was taken seriously in this competition. Keccak is a curious selection in that it is rather unbalanced towards hardware speed, while it is somewhat lacking in the software speed department. eBASH shows that on high-end processors, Keccak is slower than SHA-2 by up to 2x. Meanwhile, Keccak wipes the floor in hardware speed and die area.

For certain applications, this particular performance profile can give the advantage to an attacker. Consider the scenario of password storage, where the defender switches from PBKDF2-HMAC-SHA-2 to PBKDF2-HMAC-SHA-3. This reduces the cost of an attacker while increasing the cost of the defender, for the same number of PBKDF2 iterations. That said, this is a rather fringe case, and the defender would be better served by switching to a memory-hard key-derivation function if possible.

SHA-3 comes with a completely different design which not only provides diversity, but also fixes some of the standing issues with the aging  MD construction. It is a very elegant design, very efficient in hardware, but that sadly suffers from low software performance. Perhaps chip makers will give us a hand there, or perhaps better ways to compute Keccak will arise in the meantime.

Invisible threats and RSA

There has been much fuss regarding the recent Lenstra et al's survey on X.509 certificates (see also Nadia Heninger's independent, but similar, results), where it was shown (among other things) that over 20000 out of 6 million RSA keys out there have no security, since their public keys are easily factored.

This is a visible threat: given a set of public keys, we can tell whether they are broken. Today I want to talk about invisible threats, i.e., threats that are undetectable to anyone but their perpetrator. We often know them as "backdoors."

Young and Yung formalized the concept of such backdoors as "Secretly Embedded Trapdoors with Universal Protection", or SETUPs. A SETUP is a modification of a cryptosystem that behaves very similarly, but its output is easily breakable by an attacker (and no one else!) A SETUP must also be (polynomially) indistinguishable from a valid output of said cryptosystem.

Small roots of polynomials

What does smooth integer finding, error correction, and code-breaking have in common? They can all be represented as finding "small" roots of some integer polynomial (modulo n) and, in turn, they all come down to a lattice reduction problem.

Coppersmith, in his 1996 paper, showed how to use lattice reduction as a tool to attack RSA. In particular, he showed how given half of the bits of a public key's (\(N = pq\)) factor (obtained via, say, a side-channel attack), you can find the full factor, and thus break the key. You do this by modelling the problem as a polynomial: given \(p'\), an approximation of \(p\) within a reasonable distance of \(p\), e.g., \(<2^{256}\), find small roots of 

\[ f(x) = x + p' \pmod{p}. \]

Since we do not actually know \(p\), we use the next best thing, \(N\), a multiple thereof. The algorithm itself works by "lifting" the polynomial onto the integers, and using the well-known LLL (co-authored by A. K. Lenstra, incidentally) approach to solving said integer polynomial. LLL is fast in the "polynomial-time"-sense: given a basis of dimension \(d\) with \(n\)-dimensional vectors with norm at most \(B\), LLL finds a short (but not the shortest; that problem, SVP, is NP-hard) basis in \(d^{3+o(1)}n(d + \log B) \log B\) bit operations, or roughly \(O(d^5 \log B)\). This means bases with some hundreds of vectors of (say) 1024-bit integers will not be fast to reduce in practice, and may require hours or days to reduce.

Luckily, the Coppersmith method doesn't require very large bases (usually dimension is under 100, for 1024-bit RSA; we'll get to that later), and is often pretty fast in practice. Now, let's see the actual backdoor in practice.

An RSA backdoor

A very simple RSA SETUP was given by Crépeau and Slakmon, relying on Coppersmith's method to factor vulnerable keys. What it does is simply to embed approximately half of the bits of one of the factors of the RSA key, in the key itself. Here's some SAGE code to do this:

def rsa_bd_keygen(k): 

    """Generate backdoored RSA key with k bits. Tested with k = 1024""" 

    slack = 32 # k//4 + slack bits stored 

    beta = 0.5 # p = n^beta 

    e = 65537 

    p = random_prime(2^(k//2), lbound=ceil(sqrt(2)*2^(k//2-1)), proof=False) 

    q_ = random_prime(2^(k//2), lbound=ceil(sqrt(2)*2^(k//2-1)), proof=False) 

    n_ = p*q_ 

    tau = (n_ // 2^(7*k//8)) % 2^(k//8) 

    mu  = (p // 2^(k//4 - slack)) % 2^(k//4 + slack) 

    lam = n_ % 2^(5*k//8 - slack) 

   

    n = tau*2^(7*k//8) + mu*2^(5*k//8 - slack) + lam 

    q = n//p; q += (1^^q&1) 

    while gcd(e, q-1) > 1 or not q.is_prime(): 

        m = ZZ.random_element(2^(k//8 - slack - 10)) & -2 

        q = q^^m 

        n = p*q 

    d = e.inverse_mod(n) 

    return (p,q,n,e,d)

The above code returns an RSA modulus in which the middle \(k/4 + \text{slack}\) bits belong to the factor \(p\), and the remaining bits are randomly generated. This is not yet a SETUP: the moduli \(n\) are distinguishable from random, by using Coppersmith's method to obtain \(p\) from its upper bits. To turn this into a SETUP, one has to hide the bits, by using, e.g., encryption on the partial \(p\) information. In case our generator is a blackbox, this can be regular symmetric encryption; when the users have access to the key generation procedure, it is best to use public key methods to hide it - Young and Yung have made a living out of coming up with such methods.

To break the key generated above, we can too use SAGE:

def rsa_bd_break(n, k, eps=0.5/8):

    tau = (n // 2^(7*k//8)) % 2^(k//8) 

    mu = (n // 2^(5*k//8 - slack)) % 2^(k//4 + slack) 

    print "Solving..." 

    P.<x> = PolynomialRing(Zmod(n)) 

    f = x + p_*2^(k//4 - slack) 

    # set_verbose(2) 

    while True: 

        roots = f.small_roots(X=2^(k//4 - slack), beta=0.5, epsilon=eps) 

        if len(roots) > 0: 

            print hex(ZZ(roots[0])) 

            return ZZ(roots[0]) 

        print "Failed with eps = " + str(eps) 

        if eps/2 < epsthresh: 

            print "Quitting..." 

            break 

        print "Retrying with eps = " + str(eps/2) 

        eps /= 2 

    return None

As long as we have more than half the bits of \(p\) in \(p'\), we can find the full \(p\) in polynomial time. This does not mean it can't be slow. I have added the slack bits to increase the efficiency of the root finding, requiring the reduction of a smaller basis¹. The eps argument is used to control the size of the lattice to reduce --- the smaller it is, the larger the lattice basis will be (and the better the chances to finding a solution).

Here's an example execution:

Generating RSA key... Done. 

Original p = 11183581128574189163983793036002083746501559137516652528752284765046234959066928998151315453810766744898339995298871471424016984721754805133501061552181043

Solving... 

Failed with eps = 0.0625000000000000 

Retrying with eps = 0.0312500000000000

Recovered p = 11183581128574189163983793036002083746501559137516652528752284765046234959066928998151315453810766744898339995298871471424016984721754805133501061552181043

SAGE factors RSA-1024 bit keys, with 272 bits of \(p\) embedded, very quickly, usually under a second.

Summary

The grandfather of this sort of method is, of course, Ken Thompson's legendary talk "Reflections on Trusting Trust". The moral there was that you can't really trust code you did not fully create yourself²; in our case, it is similar: you cannot trust unreviewed, proprietary cryptographic code that behaves like a blackbox. It could be doing anything!

Backdoors like this one, be them in hardware or software, can be avoided by systematically auditing and reviewing code. If you're a vendor, you can increase your perceived trustworthiness by opening up critical routines such as key generation. As a client, you should demand that such code be thoroughly reviewed either by you, or appropriate third-parties. In today's uncertain times, when intrusions come from increasingly powerful adversaries, one can never be too careful.

[1] Lattice basis reduction, while polynomial-time, can be quite slow in practice, with complexity ranging from cubic to quintic.
[2] And even then, you may shoot yourself in the foot.

More fun with C++ metaprogramming

Since you're here, you have most certainly seen my last C++-related post, wherein I implemented compile-time AES encryption using C++ templates.

Today, I bring you CubeHash. Now, you might be wondering of what use is a compile-time implementation of CubeHash. Template metaprogramming is used here for a very specific task: to compute the initial state.

The CubeHash specification dictates that the initial 1024-bit (or 32-word) state is computed from the parameters h (output hash bit length), b (the number of bytes to mix with the state each round), and r (number of rounds) as follows:

• Place the 32-bit value h/8 in state[0];
• Place the 32-bit value b in state[1];
• Place the 32-bit value r in state[2];
• Fill state[3] through state[31] with 0;
• Apply the CubeHash round function 10r times.

To compute the initial CubeHash state, then, we have to be able to compute the full round function. And that's exactly what we did. The following C++ header file implements all possible variants of CubeHash easily, since all that changes between them are the h, b and r parameters. The implementation itself is based on the reference simple implementation, available from SUPERCOP. Switching to a faster SSE2 implementation is trivial.

Here it is: CubeHash. Have fun.