type flaw attack (idea)

A type flaw attack manipulates the raw data of a communication protocol to cause a misinterpretation of that data at the message level. Any security analysis that is based on the assumed nature of those messages will therefore fail to catch such an attack. Fortunately, the conditions required for the type flaw to arise tend to be very narrow, but guarding against them even once spotted may be difficult or impossible depending on the interaction between the protocol, cryptography and communication procedures.

In the authentication and mutual authentication writeups, a common hurdle was found: the need for a previously arranged "shared secret", the symmetric encryption key, between the protagonists. A more workable approach is for each agent to share a key with a central server, then to use this mutual trust of the server in place of a shared secret as the foundation for secure communications. For the purposes of understanding the type flaw attack, we will consider such a protocol based, as usual, on the exchange of nonces.

Otway-Rees protocol

Participants: Principals A and B; a server S
Assumptions: A and B each separately trust S, on the basis of "shared secret" symmetric encryption keys, Kas and Kbs respectively. Thus a message {M}_Kas can be created or decrypted only by A and S; whilst only B or S could create or decrypt {M}_Kbs.
Aim: To establish a key Kab known to both A and B but no other party with the exception of S (thus, A and B can then communicate securely using messages of the form {M}_Kab without further demands on the server).

Protocol
1) A → B: M,A,B,{Na,M,A,B}_Kas
2) B → S: M,A,B,{Na,M,A,B}_Kas,{Nb,M,A,B}_Kbs
3) S → B: M,{Na,Kab}_Kas,{Nb,Kab}_Kbs
4) B → A: M,{Na,Kab}_Kas

The message M is used to identify a run of the protocol; A's message {Na,M,A,B}_Kas binds her nonce to the identities of the intended participants and this run identifier M. B cannot alter this message (he lacks Kas) but having received M 'in the clear' from A, he can bundle all three identities up with a nonce of his own in a form only the server can read, {Nb,M,A,B}_Kbs.

The server knows that whilst anyone could send it M,A,B, only A and B could have created {Na,M,A,B}_Kas and {Nb,M,A,B}_Kbs; so having received all five from B can safely conclude that it is communicating with B, who must have previously received the four messages from A (which confirms that A also wishes for a shared key to be set up, not just B). Thus the server can (along with the run identifier) supply two encrypted messages to B.

One of these B can decrypt, recovering his nonce Nb and the newly assigned Kab. {Na,Kab}_Kas is incomprehensible to him, but he can forward it to A. She can decrypt it, and, reassured by the presence of her nonce Na, can conclude that the other part of the message, the key Kab could only have been assigned by S.

The type flaw attack

Or at least, that is the hope; and there is no apparent way for an intruder to manipulate the messages as messages to gain access to Kab. However, in reality, 'messages' are sent as strings of bits, with no indication of their type (nonce, name, key etc.) If conditions are just right, then the need for identifiers to be sent as both plain- and ciphertext can be exploited by an intruder to create the impression of a key from other types of message: this is the type flaw attack.

Consider the protocol from A's perspective. She sends a message with 4 submessages- 3 in plaintext, 1 encrypted such that, when decrypted, it yields 4 submessages of its own: a nonce (private to A and S) and the three identifiers (public). After some wait, a response is received which should consist of two parts- a plaintext submessage, and an encrypted part containing the nonce and a key - or rather, a string which should be interpreted as the key.

Suppose therefore that the length as bits of a string M,A,B is precisely the length of a key K. As a toy example, we will suppose that M is 8 bit, A and B are 4 bit, and keys are thus 16 bit. Picking some numbers at random to illustrate, suppose A initiates the protocol with M=01000100, A=0111, B=0011 and a nonce Na=1101. She builds the message Na,M,A,B by concatenation: this gives 11010100010001110011 - this is then encrypted by the key Kas to give some ciphertext {Na,M,A,B}_Kas; grabbing another random 20 bit number let us suppose this is 00111000001100101110. So Alice transmits the bits representing M,A,B,{Na,M,A,B}_Kas; namely 010001000111001100111000001100101110.

A legitimate recipient B would break this into appropriately sized pieces: 01000100 0111 0011 00111000001100101110; he interprets the first three pieces as M,A and B and can then construct appropriate messages for the server. However, an intruder masquerading as B can skip communication with the server entirely and send back the first and last parts M,{Na,M,A,B}_Kas: that is, the easily derived bit string 0100010000111000001100101110.

Alice then breaks this into 01000100 00111000001100101110; the first part is of course M as required. The second part is meant to be something encrypted with Kas, and indeed it is- the message Na,M,A,B as bit string 11010100010001110011. However, Alice, believing this to be the message from B containing the key, splits it not as Na,M,A,B - 1101 01000100 0111 0011 - but Na,Kab = 1101 0100010001110011. Crucially, the first four bits are her nonce Na- supposedly the sign that only S could have generated the key - whilst the remaining 16 bits is precisely the right length for a key, so the assumption is that Kab is given by those 16 bits. Worse still, although the intruder I could not have extracted these 16 bits from their encrypted form, he doesn't need to- they're the first 16 bits of the string Alice originally broadcast. So now Alice believes that she can securely communicate with Bob, when in fact the 'secret' is shared not with Bob but the intruder (who can thus impersonate Bob).

Returning to the abstraction of messages, we can describe this attack as follows:

Type Flaw attack of the Otway-Rees Protocol (Impersonation of B)
1) A → I(B): M,A,B,{Na,M,A,B}_Kas
'4') I(B) → A: M,{Na,M,A,B}_Kas

This looks like a reflection attack, but A would only be happy with the response at stage '4' under the narrow condition that length(K)=length(M,A,B) so that {Na,M,A,B}_Kas looks like {Na,K}_Kas for some K- if this is not the case, A would reject I's message and no exploit exists. However, this means that Otway-Rees is overburdened by the need to not just specify the communication protocol, but the underlying implementation, to prevent this condition being met. Alternatively, the protocol would have to call for conditional responses- A comparing the received key Kab to M,A,B for instance, and only accepting it if they differ: this may be necessary if the security procedure has no control over the communication or cryptographic processes (so cannot tell what bit strings are involved), but introduces additional computational load.

There is a stronger still type flaw attack against Otway Rees through which the intruder, now impersonating the server, can feed M,A,B as the key to both A and B- I can then eavesdrop on all subsequent communications, and moreover send messages seemingly from Alice or Bob to the other. At the message level, this can be demonstrated as follows:

Type Flaw attack of the Otway-Rees Protocol (Impersonation of S)
1) A → B: M,A,B,{Na,M,A,B}_Kas
2) B → I(S): M,A,B,{Na,M,A,B}_Kas,{Nb,M,A,B}_Kbs
3) I(S) → B: M,{Na,M,A,B}_Kas,{Nb,M,A,B}_Kbs
4) B → A: M,{Na,M,A,B}_Kas

Again, the intruder is able to generate messages that appear to be encrypted with keys unknown to him, simply by reflecting convenient sections of the observed bit strings; whilst inferring the decrypted contents of those messages from knowledge of the protocol and the rest of the bits.

As a final nail in the coffin of Otway-Rees, notice that during a legitimate run, A initiates the procedure but B has the higher communication workload since he is responsible for contacting the server. Thus the protocol also raises the possibility of denial of service attacks. Secret exchange via trusted servers is possible using nonces - there is the rather involved 7-step Needham-Schroeder protocol. An alternative approach is to use timestamps in place of nonces: a real world example of this is given by the Kerberos protocol.