Note: This is a draft posted for public comment. Please wait until it has been reviewed more thoroughly before relying on it. If you have any comments please mail them to me at <david.hopwood@lmh.ox.ac.uk>, or post them (with a reference to this page) to the newsgroup sci.crypt.

[Bold type] marks places where additional information will be added.

Recent changes:

The method for preventing known/chosen plaintext attacks on public-key algorithms has been generalized, in order to reduce the amount of ciphertext expansion it causes.

SID authentication

SID is a method for handling authentication using public key cryptography. Each user has a public key, but each pair of users who communicate regularly also know each other by separate "pseudo-public" keys. A pseudo-public key is a public key that is treated as a shared secret.

The name SID stands for "Security in Depth", i.e. the principle that secure systems should be layered, in such a way that breaking one layer does not automatically allow any of the others to be broken. For example, in protocols that use session keys, breaking a session key normally only compromises the data sent in that session, not other sessions. This is obviously a good thing, and the protocol described later tries to extend similar properties to other kinds of attack.

Suppose that Alice communicates regularly with Bob. SID has the following properties that are not true in general of protocols that provide authentication and secure channels:

Alice requires a private key in order to connect to Bob. Suppose that Eve has captured this private key, and has used it to pretend to be Alice. The next time the real Alice attempts to connect to Bob, she will detect that someone has impersonated her (and similarly with Alice and Bob exchanged).
Even if both current private keys have been compromised, if the real Alice and Bob communicate using this protocol at a later time without a man-in-the-middle, they will detect whether one or both of them was impersonated.
A passive attack on the protocol, i.e. eavesdropping a session and attempting to determine what was sent over it, requires breaking either a random public key or the session key, for each session. This applies even if all the keys that have ever been stored by Alice and Bob (as opposed to temporary keys held in memory) are known to the attacker.
Alice does not possess the information necessary for anyone to fool her into thinking they are Bob, or vice-versa.
The key exchange protocol is designed not to encrypt any plaintext that could be known to an attacker, with any key. Each block of input to the public key algorithm is unpredictable and uniformly distributed. Also, nothing is encrypted using a private key, so no additional information about any private key is available to a cryptanalyst.
For the body of the session, after key exchange, an encryption mode is used that combines a block cipher and a stream cipher to make known or chosen plaintext attacks much more difficult. A more detailed analysis of this mode is given here.
In order to perform a man-in-the-middle attack, i.e. where Alice is connected to Bob but an attacker can intercept and change messages, knowledge of two private keys is required, one that is normally held only by Alice and one normally held only by Bob.
After Alice and Bob's first session, the corresponding pseudo-public keys are themselves secret. I.e. without eavesdropping the first session, even someone who can easily break the public-key algorithm cannot get any farther without breaking a session key, or finding the pseudo-public or private keys by non-cryptanalytic means.
Pseudo-public keys are changed once per session, so the previous statement can be generalised: without eavesdropping session n, even someone who can easily break the public-key algorithm cannot attack sessions n+1 or later, except by breaking their session keys or obtaining keys by non-cryptanalytic means.
Because separate pseudo-public keys are used between each pair of users, Bob cannot cheat and impersonate Alice to another user, even if he finds the private key Alice uses to connect to him.
The time between sessions can be used to determine a level of paranoia against attacks on the public-key algorithm (for example, factoring the modulus in the case of RSA, or calculating discrete logarithms for El Gamal). If the time between two sessions exceeds the paranoia setting, a dummy session can be inserted to change the current keys. This means that the time available to crack a pseudo-public key in order to try to impersonate Alice or Bob, or to perform a man-in-the-middle attack, can be limited to whatever is desired.
To try to make man-in-the-middle attacks using compromised private keys more difficult, there is a protocol (which can be initiated at any time during a session) that forces communication to take place in simultaneous rounds. For example, Alice and Bob can simultaneously pose a list of questions to each other, then simultaneously answer them. This prevents automated MITM attacks using a simple computer program, since the man-in-the-middle needs to guess Alice and Bob's responses sufficiently well to fool both of them.
Optionally, protection against limited denial of service attacks can be implemented. If an attacker can insert records, change them, or cause them to be dropped, but some proportion of records get through correctly, the connection can continue uninterrupted using the remaining bandwidth. For this to be useful, other denial-of-service attacks on the underlying transport should also be plugged.
Any combination of public key encryption algorithm, block cipher, and stream cipher may be used. Algorithms and key lengths can be different from session to session. For example, this allows the pseudo-public key length to be increased over time, to take into account improvements in computing power or factoring algorithms. It also allows algorithms (either public- or secret-key) whose security has been found to be in doubt to be dropped with a minimum of hassle or risk.

These statements rely on each user's software being worthy of that user's trust. A cryptographic protocol cannot prevent, for example, a Trojan being installed on a user's machine that captures the plaintext of every transmission, or modifies the user's keys. Given that assumption, though, few if any other authentication systems provide comparable security against attacks that involve private keys being compromised.

Another useful property of SID is that either Alice or Bob can initiate each session, i.e. it is not necessary to fix the roles of client and server. Although this is basically an interactive protocol requiring a two-way connection, a suggestion is presented later [except that it isn't finished yet] for using SID to increase the security of one-way messaging, similar to email, where both Alice and Bob may not be on-line at the same time.

Conventions

Notation: E[K](M) - M encrypted using the key K.
          
D[K](C) - C decrypted using the key K.
          
H(X) -    X passed through the secure hash function H.

A pseudo-public key is referred to as Pxy, where 'x' is the sender of data to be encrypted using this key, and 'y' is the recipient. For example, data sent by Alice to Bob would be encrypted using Pab. Similarly, data sent by Bob to Alice is encrypted using Pba. (This only applies to data sent during the key exchange protocol; the actual communication is encrypted using a session key).

The corresponding private key is Qxy. I.e.

for all M, D[Qxy](E[Pxy](M)) = M

Any public key encryption algorithm may be used (it must be an encryption algorithm, and not only a signature scheme, or a key-exchange method like Diffie-Hellman). It is possible to use several different algorithms, if a code identifying the algorithm is embedded in each pseudo-public and private key. The protocol is designed to tolerate the fact that key encodings (even for random keys) may contain known plaintext.

The E and D notation is also used for secret-key algorithms (always referring to ECB mode). The names used for secret keys will not start with P or Q.

It is assumed to be infeasible to find collisions for a secure hash function, as well as the function being one-way.

Record format

Data sent in these protocols are packed into records (for both public- and secret-key algorithms). Each record has an integrity check field. A possible record format is given below:

|      blocksize       |                            | PL  |    |csize|
|<-------------------->|                            |<--->|    |<--->|
+----------------------+----------------------+-----+-----+-+--+-----+
|         data         |         data         | data:zeros:T:PL:check|
+----------------------+----------------------+-----+-----+-+--+-----+

T =     the record type: 0 if the record contains raw data,
        1 if it contains structured protocol data.
PL =    padding length, i.e. the number of zeros added between the data
        and the other fields. This can be measured in bits or bytes,
        depending on the granularity of the data. Its value can vary
        between 0 and blocksize-1 bits.
check = a CRC, calculated on everything except the check field itself,
        that will be used to verify that the record is correct. This does
        not need to be a cryptographic hash.

The diagram shows bits in big-endian order, i.e. most significant bit on the left (it doesn't really matter, but it's worth defining a standard, and most Internet protocols are big-endian).

The size of the check field, csize, should be based on the maximum desired probability of an error going undetected.

[Separate page on error correction and denial of service attacks not completed.] If this protection is not required, it is acceptable simply to drop the connection (possibly after sending back an error code) whenever a record with an incorrect check field is received.

It is not critical to use the exact record format above, as long as the following requirements are met:

each record must be an exact number of blocks long
it must be possible to encode arbitrary-length data
records containing raw data must be distinguishable from protocol records
each record must contain an integrity check
the probability of a random record being valid must be small.

Preventing known-plaintext attacks

Many kinds of cryptanalytic attacks are based on the cryptanalyst having known or chosen plaintext. We will conservatively not assume that the algorithms and protocols used are resistant to these attacks. For public-key encryption, the following method is used to prevent them:

Generate a random symmetric key, R.
Encrypt the plaintext using R.
Encrypt both R and the ciphertext from the previous step using the public key algorithm.

The advantage of this is that the input to the public key algorithm will be unpredictable, and will almost certainly not have any relationships that could be used to exploit weaknesses in the algorithm (regardless of whether the input contains known plaintext). This is not intended to have any effect against a direct attack against the public key algorithm (finding the private key from the public key, e.g. using factoring or by solving the discrete logarithm problem), but it is likely to prevent "clever" attacks (such as those described in [AC2 section 19.3] against RSA) based on the cryptanalyst having some information about the plaintext. In particular, a cryptanalyst will have less information than if the blocks were simply padded with random bits (in which case some bits of the input may still be known).

A previous draft suggested generating as many random bits as the message size, XORing the message with those bits, and encrypting both the result and the random bits in separate blocks using the public key algorithm. This is equivalent to using an OTP as the symmetric algorithm, but it makes the ciphertext double the size of the plaintext. The above method only adds the length of R (say, 128 bits) to the ciphertext size. Given that public key cryptography is much less efficient than symmetric cryptography, any decrease in the number of blocks required means an overall increase in speed.

In the protocol descriptions given later, E*[P](M) will be used to denote the encryption of M using the public key P, with the plaintext encoded as one or more records to prevent tampering, and the above technique applied to prevent known plaintext attacks. [This is unclear - a more formal definition is needed].

D*[Q](C) will be used to denote the inverse operation, i.e. decryption of C using the private key Q. Decryption is considered to have failed if the checksum is incorrect.

Key usage

The key pair for sending information from Alice to Bob is Pab/Qab, and the key pair for sending information from Bob to Alice is Pba/Qba. Alice knows {Pab, Qba}, and Bob knows {Pba, Qab}. In some public key algorithms a public key can be inferred from the corresponding private key, in which case Alice will also know Pba and Bob will know Pab, but this is not required.

The first time Alice and Bob wish to communicate, they must exchange 'public introduction keys'. For that session, the following assignments are made:

Pab := Pb (Bob's public introduction key)
Qab := Qb (Bob's private introduction key)
Pba := Pa (Alice's public introduction key)
Qba := Qa (Alice's private introduction key)

Public introduction keys should be signed by either a trusted certification authority, or a trusted signer in a system similar to the PGP web of trust. Note that introduction is the most vulnerable part of the system; if a user can be fooled into accepting a false introduction key, he/she will not necessarily detect that it is the wrong key. These keys are also targets for attacks against the public key algorithm.

However, handling certificate revocation is less of a problem in this system. If Alice finds that her public introduction key has been compromised, but this was not due to her whole key database being compromised, she can continue to communicate without interruption with correspondents for which she already has pseudo-public keys. The same applies if a CA's key is compromised; stored pseudo-public keys will continue to be valid.

It is recommended that public keys be checked by asking the CA directly, or by checking a certificate revocation list that is known to be up-to-date (for example because it was obtained recently over a secure channel to the CA). Because certificates need to be checked only on introductions, this does not require an excessive amount of bandwidth.

SID key exchange protocol

This protocol will be extended slightly later to handle key update, and to specify precisely the times at which key database entries are locked, but the basic ideas will remain the same. There are three steps:

1) Alice wants to connect to Bob. She is known to Bob by the identifier Iba. [Need to talk about the possibilities for preventing traffic analysis; for the time being assume Iba is Alice's username.] She generates a new pseudo-public/private key pair, P'/Q', and sends

Iba, E*[Pab](P')

2) Bob looks at Iba to determine which user is making the connection; he uses it to look up Pba and Qab. If there is no such user, he ends the connection. Otherwise, he decrypts the message using Qab to find P', and verifies that the resulting record has a valid check field. Then he generates a random string S, and sends

E*[Pba](E*[P'](S))

At this point Bob deletes P'. If the "simultaneous communication" protocol described later (a variant of Rivest and Shamir's Interlock protocol) is needed, he retains H(P', S) for use in that protocol.

3) Alice decrypts using Qba and Q' (verifying in each case that the result has a valid check field) to find S. She deletes P' and Q', retaining H(P', S) if the simultaneous communication protocol is needed.

At this point both Alice and Bob know S. If a man-in-the-middle who does not know Qab and Qba has changed either of the messages sent in step 1 or 2, they will end up with different values for S; in that case no data can be correctly sent, because of the check field in each record. P' and Q' are only used once, and are deleted immediately after the key exchange.

S is split into two keys: S1 and S2. S1 will be used as the session key for a block algorithm. S2 will be used as part of the seed for a keystream generator. These uses determine what their lengths will be (they need not be the same length).

A separate page describes an encryption mode called KECB; S1 and S2 are used as parameters to initialise this mode. All messages in the current session will be encrypted using KECB.

If it is required to detect possible attacks before sending any application data, the first record sent by both Alice and Bob should contain a random string. The first received record's check field should be tested before continuing (its contents are otherwise ignored). Alternatively, use the extended key exchange protocol described later, which automatically detects attacks.

If an unreasonable amount of time passes before the first record is received correctly, or between two steps in the above protocol, the implementation should time out and end the connection.

Rationale

Step 1) - Alice sends Iba, E*[Pab](P')

The reason for creating a new public/private key pair is to limit the damage that can be done if an attacker later learns information that is currently secret. Suppose that Eve records the current session, and at some point in the future obtains Bob's private key, Qab, for example by breaking into Bob's server by an unrelated attack. (She could also know Qba; it doesn't matter in this case). Knowing Qab enables her to find P'. However, she does not know Q' (and Q' is never stored permanently), so she still cannot read what was sent in the earlier session. Doing that would require a separate attack, for example solving whichever hard problem the public key algorithm is based on, or brute-forcing the session key.

P' is only used once to encrypt the session key, so cryptanalytic attacks on it that require known or chosen plaintext are not feasible.

In operating systems that support virtual memory, care should be taken that temporary keys such as P' and Q' are not paged to disk. If they are paged to disk, the protocol will still be reasonably secure, but it won't give all the guarantees that it should be able to give. In some operating systems a kernel-mode device driver may be required to allocate non-paged memory. [Link to description of the primitives that should be provided by such a driver.]

Step 2) - Bob sends E*[Pba](E*[P'](S))

For Bob to encrypt S correctly using P', he must have received P' in step 1. Therefore, he must have known Qab in order to be able to decrypt that message. He must also know Pba in order to do the outer encryption. For Alice to receive S correctly, she must know both Q' and Qba (as well as Pab to send the message in step 1). Therefore, if Alice and Bob have the same value for S, they have been correctly authenticated.

Note that Bob can choose the session key. Some protocols require the session key to be generated as a hash of random data from both Alice and Bob, in order to prevent a man-in-the-middle attack. That is not needed in this protocol: suppose Mallory is sitting between Alice and Bob and is able to read or change messages, but either does not know Qab (and therefore P'), or does not know Pba. He cannot find a value to put in place of E*[Pba](E*[P'](S)) that will allow him to know the session key.

Key update

The protocol above works even if Pab and Pba are public (in fact, that is the case in the first session between a pair of users). To achieve the additional security described earlier, in particular, the ability to detect impersonators, these keys must be updated to new secret values in each session before any data is sent.

Each user requires a key database, which must support locking and atomic updates of individual entries. The ability to update a user's database distinguishes that user from an impersonator. For example, if Mallory uses Alice's keys to connect to Bob, he will still not be able to update Alice's database. Therefore, Alice and Bob's keys will become out-of-sync, and this will be detected by Alice the next time she attempts to connect to Bob.

We must assume that a network failure, an active attack that terminates the session, or a crash of Alice and/or Bob's machine can occur at any time during the key update. That means that, for example, when the Pba/Qba key pair is being updated, there is a period of uncertainty when Alice does not know whether Bob has updated his copy of Pba yet. Therefore, Alice must temporarily store both the old and new values of Qba, so that she is guaranteed to be able to decrypt messages sent by Bob in the next session. After Alice has received confirmation from Bob that he has updated his copy of Pba, she can (and should) delete the old Qba.

[It would also be possible to do this the other way around; e.g. have Bob store two possibilities for Pba, rather than Alice store two possibilities for Qba. In that case it would sometimes be necessary to send two sets of messages encrypted with different public keys during the key exchange, so this way is simpler.]

The record for a database entry might look something like this:

record UserKeyEntry {
    PrivateKey Q_other_self;
    PrivateKey Q_other_self_new; // may be null
    PublicKey P_self_other;
}

Updates to each key entry must be atomic (even if a hardware failure occurs during the database update). A variant of Challis' algorithm can be used to ensure this. [Include link to brief description of the algorithm, and talk about possible problems due to write-behind caching.] If the database may be used by more than one thread or process, entries must be locked so that keys are updated exactly once per successful use.

When Alice and Bob are first introduced, Qab_new and Qba_new are set to null.

Below is a modified description of the key exchange that specifies precisely when key entries are locked, and includes a protocol for key update. (Note that ending the connection should cause both parties to unlock the key entries in their respective databases, if they are currently locked.)

1) Alice wants to connect to Bob. She is known to Bob by the identifier Iba. She generates a new pseudo-public/private key pair, P'/Q', then locks the entry for Bob in her key database. She sends

Iba, E*[Pab](P')

2) Bob looks at Iba to determine which user is making the connection. If there is no such user, he ends the connection. Otherwise, he locks the corresponding key entry, and finds Pba, Qab, and Qab_new. He tries to decrypt the message using Qab and (if it is non-null) Qab_new. If exactly one of the results has a valid check field, it is taken as P'. If neither are valid, Bob ends the connection, in such a way that Alice will interpret this as meaning that she may have been impersonated. [More detail needed, including specifying how to prevent someone from causing impersonation false-alarms as a denial-of-service attack.] It should not happen that both results are valid, but if it does, the connection is also ended.

To continue, Bob generates a random string S, and two new key pairs: Pab_update/Qab_update, and P''/Q''. If P' was decrypted using Qab_new, he commits { Qab := Qab_new, Qab_new := Qab_update } to his key entry for Alice. If it was decrypted using Qab, he commits only { Qab_new := Qab_update }. Then he sends

E*[Pba](E*[P'](S, P'', Pab_update))

At this point Bob deletes P'. If the "simultaneous communication" protocol described later is needed, he retains H(P', S) for use in that protocol.

3) Alice decrypts using Qba and (if it is non-null) Qba_new. If exactly one of the results has a valid check field, it is decrypted using Q' to find S, P'', and Pab_update. If neither are valid, Alice ends the connection, in such a way that Bob will interpret this as meaning that he may have been impersonated. It should not happen that both results are valid, but if it does, the connection is also ended.

Alice now deletes P' and Q', retaining H(P', S) if the simultaneous communication protocol is needed. She generates a new key pair, Pba_update/Qba_update. If the outer decryption of the previous message was done using Qba_new, she commits { Qba := Qba_new, Qba_new := Qba_update, Pab := Pab_update } to her key entry for Bob. If it was done using Qba, she commits only { Qba_new := Qba_update, Pab := Pab_update }. In either case, she sends

E*[P''](Pba_update)

Then she deletes P''.

4) Bob decrypts the last message and verifies that it has a valid check field, then deletes P''. He commits { Qab := Qab_update, Qab_new := null, Pba := Pba_update } in the key entry for Alice, and unlocks the entry. He generates a random value R (big enough to just fill a block), and sends

E*[Pba_update](R)

After this Bob can start sending application data (encrypted using S in KECB mode) immediately.

5) Alice decrypts the last message and verifies that it has a correct check field (R is not used). She commits { Qba := Qba_update, Qba_new := null }, and unlocks the entry. After this she can also start sending application data (encrypted using S in KECB mode) immediately.

[Rationale needed, especially for the use of P''.]

Simultaneous communication

Suppose that Mallory arranges for Alice to think that his public key is Bob's, and for Bob to think that his public key is Alice's. Alice now connects to Bob with Mallory trying to act as man-in-the-middle.

The following idea can be used to try to prevent man-in-the-middle attacks, or at least make them difficult to automate:

both Alice and Bob prepare a question, or list of questions.
they send the questions simultaneously.
they then send the answers simultaneously.

Mallory will find it difficult to act as man-in-the-middle in this case, because he cannot relay both Alice's responses to Bob, and Bob's responses to Alice. Instead, he must guess what either Alice or Bob would have said well enough to fool the other party (and in a limited amount of time).

A variant of the interlock protocol [Interlock84], [AC2 section 3.1] is used for each round of simultaneous communication:

Let Ma = Alice's message
    Mb = Bob's message
    I =  H(P', S) (saved from the key exchange)
    n =  a number than is not re-used between rounds

I acts as a session identifier; it will be different for the sessions between Alice and Mallory, and between Mallory and Bob. (This is true because P' is chosen by one side of the connection, and S by the other, and so Mallory cannot cause the same I to be chosen for both sessions.)

The whole exchange is encrypted using the session key in KECB mode as normal.

1) Alice sends

H(I, n, Ma)

2) Bob sends

H(I, n, Mb)

3) Alice sends

Ma

4) Bob verifies that Ma, I, and n are consistent with the hash sent in step 1. He sends

Mb

5) Alice verifies that Mb, I, and n are consistent with the hash sent in step 2.

[How is this initiated? (Probably using protocol records, in which case their format needs to be specified.) Also need a rationale.]

Terminating a session

[More work needed; in particular distinguishing normal termination from suspicious termination, and what conclusions the user should reach from a suspicious termination.]

Performance considerations

SID is more expensive than many other cryptographic protocols, because of the need to generate key pairs in each session (specifically, for the version that supports key update, both Alice and Bob have to generate two key pairs).

The public key algorithm is not specified, and AFAIK, there are no special considerations needed for particular algorithms (the padding method described earlier fixes several common security problems). So, an algorithm with short key generation times can be chosen. ElGamal may be a good choice because it does not necessarily require large primes to be generated for every key.

A potentially very useful speed-up can be obtained by pre-calculating key pairs before they are needed. This reduces the latency before each connection can be started, and allows key generation to be interleaved with other processing. Be careful that these key pairs cannot be paged to disk.

Note that in the normal case, an attacker will not know Pab or Pba, and therefore can't attempt to break them by factoring or calculating discrete logarithms. This is not a valid reason for choosing shorter keys, however, because if the pseudo-public keys are easily breakable, SID key exchange loses many of its advantages over a more straightforward shared-secret scheme.

An attempt has been made to optimize the number of messages during key exchange (on the basis that the latency introduced by round-trip network communications will continue to be significant, even if data transfer gets faster). Other aspects have not been optimised (in particular, it is probably possible to reduce the number of public key encryptions that need to be done).

[Say more about absolute times on typical hardware.]

Legal stuff

I won't be patenting any of these ideas; consider them public-domain. Parts of SID key exchange were inspired by EKE [EKE92], [AC2 section 22.5], which is patented by Steve Bellovin and Michael Merritt [EKEPatent]. I don't have a copy of that patent, or know precisely what it covers.

KECB (i.e. chaining a block cipher with a stream cipher) is not a new idea; I've just given it a name and provided justifications for using it. As far as I know, the treatment of pseudo-public keys described here is new.

Software that implements SID is unlikely to be exportable from the U.S. under the EAR regulations, regardless of what algorithms are used. For details of regulations in other countries, see Bert-Jaap Koops' Crypto Law Survey.

The Diffie-Hellman patents, claimed to cover public-key cryptography in general, will expire in October 1997. The expiry date was originally April 1997, but has changed due to a GATT agreement that affects the term of U.S. patents (the term is now either 17 years from issue or 20 years from filing, whichever is later). After October this will leave ElGamal and possibly other algorithms unpatented.

To avoid patents on symmetric algorithms, I recommend something like Blowfish for the block cipher, and RC4 for the stream cipher.

References

[Interlock84]: R. L. Rivest and A. Shamir
"How to expose an eavesdropper"
Communications of the ACM, volume 27 number 4 pp 393-395, April 1984
[EKE92]: S. M. Bellovin and M. Merritt
"Encrypted Key Exchange: Password-Based Protocols Secure Against Dictionary Attacks"
Proceedings of the 1992 IEEE Computer Society Conference on Research in Security and Privacy, pp 72-84, 1992
[EKEPatent]: S. M. Bellovin and M. Merritt
"Cryptographic Protocol for Secure Communications"
U.S. Patent #5,241,599, 31 August 1993
[AC2]: Bruce Schneier
Applied Cryptography 2nd edition: protocols, algorithms, and source code in C
Published by John Wiley and Sons, 1996
ISBN 0-471-11709-9

David Hopwood
<david.hopwood@lmh.ox.ac.uk>

Notation:	E[K](M) -	M encrypted using the key K.
	D[K](C) -	C decrypted using the key K.
	H(X) -	X passed through the secure hash function H.

T =	the record type: 0 if the record contains raw data, 1 if it contains structured protocol data.
PL =	padding length, i.e. the number of zeros added between the data and the other fields. This can be measured in bits or bytes, depending on the granularity of the data. Its value can vary between 0 and blocksize-1 bits.
check =	a CRC, calculated on everything except the check field itself, that will be used to verify that the record is correct. This does not need to be a cryptographic hash.

Let	Ma =	Alice's message
	Mb =	Bob's message
	I =	H(P', S) (saved from the key exchange)
	n =	a number than is not re-used between rounds