Scatter Chat module cryptographic protocol This DEVELOPER document describes how the cryptographic sessions between peers are established. TERMS: Keys: Sa_PUB: Public signature key belonging to buddy A. Sa_PRIV: Private signature key belonging to buddy A. Sb_PUB, Sb_PRIV: Same as above, except belonging to buddy B. Ea_PUB: Public encryption key belonging to buddy A. Eb_PUB: Public encryption key belonging to buddy B. Cryptographic Functions: Enc_G(K, data): 2048-bit ElGamal encryption of data with key K. Sig_D(K, data): 1024-bit DSA signature of data with key K. Enc_AES(K, data): 256-bit AES ECB-mode encryption of data with key K. HMAC(K, data): 256-bit SHA-1 HMAC of data with key K. Padding Function: HPAD(s, d): Inserts a random byte for every three bytes of the 32-byte sequence number s, then appends all 20 bytes of the message digest d to the end to create a 64-byte padded header using a total of 12 random bytes. MPAD(data): Inserts a random byte for every three bytes of data, then appends random bytes until resulting block is aligned to 32 bytes. Buddy A Buddy B (Initiator) | | | | | +----+----+ | | Sa_PUB |--------------------------------------->+ +----+----+ | | | +-----------+------------+ | | Ea_PUB || |------------------------------->+ (1a) | Sig_D(Sa_PRIV, Ea_PUB) | | +-----------+------------+ | . | (2) . +----+----+ +<---------------------------------------| Sb_PUB | . +----+----+ . | . +-----------+------------+ (1b) +<--------------------------------| Eb_PUB || | . | Sig_D(Sb_PRIV, Eb_PUB) | . +-----------+------------+ . . . . . . (2) . . . . +----------------+------------------+ . | Let session_stuff_1 = | . | (key_1 || iv_1 || | . | hmac_1 || seq_num_A) |------------------------->+ (3) | | . | Enc_G(Eb_PUB, session_stuff_1 || | . | Sig(Sa_PRIV, session_stuff_1)) | . +----------------+------------------+ . . . . . . +--------------------+--------------+ . | Let session_stuff_2 = | . | (key_2 || iv_2 || | (3) +<-----------------------| hmac_2 || seq_num_B) | . | | . | Enc_G(Ea_PUB, session_stuff_2 || | . | Sig(Sb_PRIV, session_stuff_2)) | . +--------------------+--------------+ . . . . (4) . session_key = key_1 XOR key_2 . . session_iv = iv_1 XOR iv_2 . . session_hmac = hmac_1 XOR hmac_2 . . . . . . . +----------------+--------------------+ . | Let A = MPAD(message) | . | | . | Let B = HPAD(seq_num_B++, | . | HMAC(session_hmac, A)) | . | | . | Enc_AES(session_key, A || B) |----------------------->+ (5) +----------------+--------------------+ . . . . . NOTES: (1): After receiving the remote buddy's public signature key and public encryption key, the local buddy checks that the encryption key's signature is valid using the signature key that was just received. If invalid, the handshake is immediately aborted. Otherwise, the signature key's fingerprint is compared with the version in the local key database. If no matching fingerprint is found in the database, the user is prompted with the key fingerprint and given the option to accept or reject the key. If the user rejects the key, the handshake is aborted. (1a): Notice at this point that the initiator, buddy A, has revealed the fact that encryption is being used to buddy B and any entity sniffing the network. However, if buddy B chooses not to accept the key for any reason, then no response is sent whatsoever, and no one can tell if B is using encryption at all. (2): After the buddy sends its public keys, it enters an asynchronous phase of the handshake (marked with a dotted line). During this time, the encrypted session setup information can be sent without waiting for any event. (3): Each buddy will generate 1024 bits of random data. These bits are split into four parts, each 256-bits long: an AES session key, an AES session initialization vector (IV), an HMAC key, and a sequence counter. This 1024-bit block is signed and encrypted, then sent to the peer. (4): Once each buddy has sent & received the setup information from (3), the final message encryption key, IV, and HMAC key are generated by XOR'ing the two parts together. This implements Perfect Forward Secrecy. At this point, both buddies have the same exact message key, IV, and HMAC key. The handshake is now complete. (5): A buddy sends an encrypted message by padding the message, appending the incremented sequence number (see Replay Attacks section), then encrypting it with AES-256 (in ECB mode) along with the HMAC of the padded message and sequence number. Analysis of ECB Mode AES encryption is done in ECB mode so that full duplex communication can be achieved. Notice in step (5) that the compontents of the AES-encrypted block are the sequence number, the message, and the sequence number/padded message HMAC digest. The message is padded with the MPAD function; this prevents any two identical messages from resulting in the same ciphertext blocks. The HMAC digest is dependent upon the padded message, thus its entropy propigates to the HMAC's output. The sequence number is a 32-byte value that is incremented for each message to prevent replay attacks. The HPAD function mixes in random bytes it in a similar fashion as MPAD. As a result, each 4-byte block of the plaintext has at least one random byte; this prevents any two identical plaintext blocks from resulting in the same ciphertext block. Authentication Authentication is performed with DSA signatures. The initiator first sends the public signing key, then sends the public encryption key along with a signature on this encryption key. If the key's signature validates with respect to the public signature key that was just sent, then the receiving buddy will check the signing key's fingerprint against the local trusted fingerprint database. If the local trust database does not know about the fingerprint, then the user is prompted for manual confirmation. This authentication mechanism is similar to the "anarchy model" used by SSH clients. Secrecy Immediately after the buddies have authenticated each other in (1a) and (1b), the session setup info is exchanged using each other's encryption keys. Once the session is started, then the created AES key is used for all messages (the AES key is created by XOR'ing random bits from both buddies in (4)). Thus, every possible piece of information is encrypted which ensures that secrecy is preserved. Replay attacks Replay attacks are thwarted through the use of sequence numbers exchanged in (3). Each buddy generates a random 256-bit sequence number for use by the opposite buddy. Once the handshake is completed, a buddy wishing to send a message must first increment the sequence number given by the opposite buddy by 1 and encrypt this value along with the message. This mechanism prevents replay attacks because old encrypted messages will have different sequence numbers than what is necessary for the current session because they are randomly generated anew each time. The chances that the current session's sequence number is the same as an older session's is 1 / (2 ^^ 256). Furthermore, the sequence numbers are always encrypted, both during the initial exchange in (3), but also when they are used during message processing in (5). At no point in time will an evesdropper find the plaintext version of the sequence numbers. Also, the sequence numbers are mixed into the HMAC calculation, further ensuring their dependence to the specific message to which they belong. Note that an attacker could still use old messages to initiate a new connection only since the sequence numbers are not checked until a new message is sent. This weakness would allow an attacker to receive encrypted messages from a completely unsuspecting buddy. The attacker would not be able to read the messages, but they may be able to conduct enhanced traffic analysis depending on the upper communications layer. The upper layer can (and should) protect against this weakness by portraying a connection as 'unverified' until a valid message is received from the buddy. Assuming that the random number generator used in this system is cryptographically random, it is safe to conclude that replay attacks are not possible, with the exception of the weakness mentioned above. Traffic analysis Traffic analysis is possible against any communications system. The true extent to which traffic analysis yields useful information is ultimately bound by the system's end use; in most cases, this is not controllable by the system designer. However, there can be features included by the designer to frustrate analysis. This system employs one such feature: message padding. All messages sent over the wire are padded with random bytes. For each three plaintext bytes in the message, a fourth random byte is inserted. This causes identical plaintext messages to result in differing ciphertexts; an evesdropper will not be able to tell that the same message was sent multiple times. The padding function also aligns all messages to the nearest 32-byte boundary. This effectively obscures the message length when relatively short messages are exchanged (for example, in instant messaging applications). Note that for systems exchanging larger messages, this byte alignment may be insufficient.