TStreamCipher

0

TForge 0.76 is released.

The release introduces a new class TStreamCipher. The name TStreamCipher does not mean that the class supports stream cipher algorithms only, such as Salsa20 or RC4 – it supports all cipher algorithms currently implemented in TForge, like TCipher class does; block ciphers are converted into stream ciphers using CTR mode of operation.

The initial motivation to write TStreamCipher class was to generate “solid” byte-wise keystream. TCipher class generates block-wise keystream; to obtain solid byte-wise keystream you need to maintain additional state, and that’s what the TStreamCipher class is doing. Here is the code sample illustrating the above:

const
  Nonce = 42;

var
  Cipher: TCipher;
  StreamCipher: TStreamCipher;
  Key: ByteArray;
  KeyStream, KeyStream1, KeyStream2: ByteArray;

begin
// create 128-bit AES key:
  Key:= ByteArray.AllocateRand(16);

// generate 16 bytes of keystream:
  KeyStream:= TCipher.AES.ExpandKey(Key, CTR_ENCRYPT, Nonce).KeyStream(16);
  Writeln(KeyStream.ToHex);

// generate 8 + 8 bytes of keystream:
  Cipher:= TCipher.AES.ExpandKey(Key, CTR_ENCRYPT, Nonce);
// Warning - KeyStream1:= Cipher.KeyStream(8) + Cipher.KeyStream(8) is wrong
//   because the compiler does not evaluate the summands in order
  KeyStream1:= Cipher.KeyStream(8);
  KeyStream1:= KeyStream1 + Cipher.KeyStream(8);
  Writeln(KeyStream1.ToHex);
  Assert(KeyStream <> KeyStream1);

// generate 8 + 8 bytes of keystream using TStreamCipher instance:
  StreamCipher:= TStreamCipher.AES.ExpandKey(Key, Nonce);
  KeyStream2:= StreamCipher.KeyStream(8);
  KeyStream2:= KeyStream2 + StreamCipher.KeyStream(8);
  Writeln(KeyStream2.ToHex);
  Assert(KeyStream = KeyStream2);
end;

The Cipher instance generates 8 + 8 bytes of keystream by taking the first 8 bytes from the first block and the second 8 bytes from the second block (AES block size is 16 bytes), that is why the generated keystream is different.

The code also illustrates the use of Nonce. The purpose of nonce is to encrypt multiple messages (ex files) with the same secret key – each message should be encrypted with unique non-secret nonce. Modern cryptoalgorithms such as Salsa20 have built-in support for nonce, and TForge supported the feature since version 0.71; old block cipher algorithms such as AES allow to implement the same feature using IV (initialization vector), and this is the second thing that TStreamCipher class is doing; TStreamCipher API does not expose IV of the underlying cryptoalgorithm, it exposes Nonce only.

Nonces are now supported by both TStreamCipher and TCipher classes, as the above code sample shows; there is a limitation though: the block size of an algorithm should be 128 bits at least; that means you can’t use nonces with legacy 64-bit block ciphers such as DES or Triple DES.

TForge 0.76 includes new demo project FileEncryptDemo (Demos\Ciphers folder) which shows how to use TStreamCipher. The idea of the project is to implement secure encryption of multiple files with a single key (and multiple non-secret nonces) and transparent reading of the encrypted files.

Hensel’s lifting

0

Number theory is full of gems that turn into effective algorithms demanded in cryptography. Consider the congruence

x N \equiv 1 \mod R

where N is odd, and R > N is a power of 2.

Probably the most effective algorithm to solve it is based on the Hensel’s lemma; the corollary that applies for our congruence is: suppose we know the solution x_{k-1} for R=2^{k-1} :

x_{k-1}N \equiv 1 \mod 2^{k-1}

then the solution x_k for

x_k N \equiv 1 \mod 2^k

is either x_{k-1} or x_{k-1} + 2^{k-1}

Example: solve

x \cdot 21 \equiv 1 \mod 32

We start with the trivial

x_1 \cdot 21 \equiv 1 \mod 2

which can be nothing else but x_1 = 1; next,

x_2 \cdot 21 \equiv 1 \mod 4

which can be either x_2 = 1 or x_2 = 1 + 2 = 3; checking the first alternative gives 1\cdot 21\ and\ 3 = 1, so x_2=1; next,

x_3 \cdot 21 \equiv 1 \mod 8; checking x_3 = x_2 = 1 gives 1\cdot 21\ and\ 7 = 5, so x_3=x_2+4=5; next,

x_4 \cdot 21 \equiv 1 \mod 16; checking x_4 = x_3 = 5 gives 5\cdot 21\ and\ 15 = 9, so x_4=x_3+8=13; finally,

x_5 \cdot 21 \equiv 1 \mod 32; checking x_5 = x_4 = 13 gives 13\cdot 21\ and\ 31 = 17, so x_5=x_4+16=29.

The solution of the congruence is x = 29.

Serial Number System Challenge

6

I stumbled across an interesting link that made me think about a solid serial number system based on strong cryptography. Cryptography discourages systems based on secret algorithms, and relies on open algorithms and secret keys. So let us develop a serial number generation/verification system with the same usability as the one in the linked article but without any secret algorithms.


First, our serial numbers should have the form

XXXX-XXXX-XXXX-XXXX-XXXX

where X – an uppercase english letter A..Z; to prevent user’s confusion let us exclude the letter O which looks like zero, so in the end we have 25 possible letters in 20 positions, that is BigInteger.Pow(25, 20) = $1D6329F1C35CA4BFABB9F561 combinations. Next, we want to work with full bytes; this reduces the possible serial keys to 11 byte-long numbers; also we want to use 2 bytes of serial key as a key checksum; this leaves us with 9 bytes, and we have 9*8 = 72-bit serial keys. That should be strong enough against full keyspace search attack on our system.


Suppose you are a micro-ISV and expecting to sell up to 100 copies of you software; then you need to generate 100 72-bit keys and embed their hashes into the executable (if it will turn out later that you need more copies it is not a problem – just recompile your executable with more keys next time; the same way you can revoke leaked keys – by not including them in the next release).

To derive 72-bit keys I use 128-bit master key and AES encryption algorithm as a pseudorandom function. Note that the 128-bit master key is actually the only secret in the system, everything else is calculated. It is worthwhile to generate the master key, for example, by tossing a coin 128 times.

For hashing I use SHA256 hash function. I also use CRC16 algorithm to calculate the key checksums.


The verification is 2-phase process. First, it converts a serial number in 20-letter format entered by user into a 11-byte serial key, calculates the checksum of the first 9 bytes and compares it with the last 2 bytes (this prevents user from mistyping his serial number). Second, it hashes the 9-byte key and checks that the hash exists in the keyhash table.


And now the challenge. The last TForge release (0.74) includes full source code of console application with the serial number system described above, in the Demos\Challenge subfolder. The key generation code is also included, though it is not used in the application and could be kept secret; the only thing I keep secret is 128-bit master key used.

Build the application with Delphi or Lazarus/Free Pascal.

One of the valid serial numbers is:

AVVH-GJCX-YVWM-EHUE-YMRL

Try to find other valid serial number(s).

Salsa20 support explained

10

Salsa20 is a stream cipher; like any stream cipher Salsa20 encrypts/decrypts data by xor‘ing a plaintext/ciphertext with a pseudorandom keystream.

Salsa20 generates keystream by hashing 64-byte (512-bit) blocks; the block consists of 4 parts:

  • fixed “magic words” – 16 bytes
  • key – 32 bytes
  • nonce (message number) – 8 bytes
  • block number – 8 bytes

This simple structure allows to generate 64-byte blocks of keystream independently; to generate an arbitrary block of the keystream one need to set the block number in the cipher’s state and hash the 64-byte block.

TCipher class supports Salsa20 design by following methods:

function TCipher.SetIV(const AIV: ByteArray): TCipher;
function TCipher.SetNonce(Value: UInt64): TCipher;
function TCipher.Skip(Value: UInt64): TCipher;

TCipher class considers concatenated nonce and block number as initialization vector (IV). The TCipher.SetIV sets both the nonce and the block number in the cipher instance state. [Corrected – changed in ver 0.71]

The TCipher.SetIV  and TCipher.SetNonce methods do the same – set the nonce field in the the cipher instance state and clear the block number field; the difference is that TCipher.SetIV accepts the parameter as a byte array while TCipher.SetNonce as an integer.

The TCipher.SetIV method was introduced mainly for testing purposes.

The purpose of nonce is to serve as a unique message number; a nonce need not be kept secret, but it should never repeat during the lifetime of a secret key.

As an example suppose we want to encrypt several files by a single secret key; the right way to do it is to encrypt each file with a unique nonce value, like this:

procedure EncryptFiles(const Key: ByteArray; FileNames: array of string);
var
  Cipher: TCipher;
  Nonce: UInt64;
  I: Integer;

begin
  Nonce:= 0;
  for I:= 0 to High(FileNames) do begin
    Cipher:= TCipher.Salsa20;
    Inc(Nonce);
    try
      Cipher.ExpandKey(Key)
            .SetNonce(Nonce)
            .EncryptFile(FileNames[I], FileNames[I] + '.salsa20');
    finally
      Cipher.Burn;
    end;
  end;
end;

The try .. finally block ensures that the sensitive key data in the cipher instances’ states is destroyed.

The TCipher.Skip method increments the block number field in the cipher instance state; its purpose is to implement parallel encryption/decryption as was demonstrated in the previous post.

TCiphers

2

TForge 0.70 is released.

The release adds a new package TCiphers implementing private-key cryptography (block and stream ciphers). The current release supports:

  • Block Ciphers:
    • AES
    • DES
    • RC5
  • Modes of operation
    • ECB
    • CBC
    • CTR
  • Padding methods
    • No padding
    • Zero padding
    • ANSI X.923
    • PKCS
    • ISO 10126
    • ISO/IEC 7816-4
  • Stream Ciphers
    • RC4
    • Salsa20

The main idea behind writing the package is user-friendly Pascal Crypto API, suitable both for writing production code and for learning cryptography. Here is an example (the full source code can be found in the CipherDemo project) demonstrating how to encrypt and decrypt a file using AES cipher and CBC mode of operation in TForge:

procedure CBCFileDemo(const FileName: string;
                      const IV, Key: ByteArray);
begin
  TCipher.AES.ExpandKey(Key, CBC_ENCRYPT, IV)
             .EncryptFile(FileName, FileName + '.aes');
  TCipher.AES.ExpandKey(Key, CBC_DECRYPT, IV)
             .DecryptFile(FileName + '.aes', FileName + '.bak');
end;

The above example requires some explanation. For security reasons TForge don’t keep a copy of a plaintext key in a state of cipher instance if an algorithm supports key expansion (aka “key schedule”) procedure; instead it immediately expands a plaintext key passed as a parameter of ExpandKey method into a form internally used by the algorithm. A key expansion procedure may generally be affected by the encryption direction (encryption/decryption) and mode of operation, that is why TForge requires to set the encryption direction explicitly. If you expand key for decryption (ex using CBC_DECRYPT flag) and then call encryption method (ex EncryptFile), TForge raises exception.

The example is more suitable for crypto exercises. Production code usually follows the next template:

  • create a cipher instance
  • use the cipher instance for encryption or decryption
  • erase the key data from the instance

which can be implemented as follows:

var
  Cipher: TCipher;

begin
  Cipher:= TCipher.AES.ExpandKey(Key, CBC_ENCRYPT, IV);
  try
    Cipher.EncryptFile(FileName, FileName + '.aes');
  finally
    Cipher.Burn;
//    Cipher.Free;
  end;

The instances of the TCipher type support Free method but there is no need to call Free explicitly because an instance is freed automatically when it goes out of scope.

If the padding method is not set explicitly TForge applies “default” padding method which depends on the mode of operation used. Ex for the CBC mode of operation the default padding method is “PKCS”, for the CTR mode of operation the default padding method is “no padding”; if you need say CTR with PKCS padding declare the padding method explicitly:

  Cipher:= TCipher.AES.ExpandKey(Key, CTR_ENCRYPT or PADDING_PKCS, IV);

TCipher type includes several helper methods to keep simple tasks simple; for example to encrypt/decrypt a single 64-bit block by DES cipher with a given key

procedure BlockDemo(const Block, Key: ByteArray);
var
  CipherText, PlainText: ByteArray;

begin
  CipherText:= TCipher.DES.EncryptBlock(Block, Key);
  PlainText:= TCipher.DES.DecryptBlock(CipherText, Key);
  Assert(PlainText = Block);
end;

the methods EncryptBlock and DecryptBlock keep the key expansion details under the hood.

Another handy pair of TCipher methods is designed to encrypt/decrypt arbitrary-sized data:

procedure CBCDemo(const PlainText, IV, Key: ByteArray);
var
  CipherText, Plaintext2: ByteArray;

begin
  CipherText:= TCipher.AES.ExpandKey(Key, CBC_ENCRYPT, IV)
                          .EncryptData(PlainText);
  PlainText2:= TCipher.AES.ExpandKey(Key, CBC_DECRYPT, IV)
                          .DecryptData(CipherText);
  Assert(PlainText = PlainText2);
end;

The core TCipher methods for encryption/decryption of arbitrary data are

    procedure TCipher.Encrypt(var Data; var DataSize: LongWord;
                      BufSize: LongWord; Last: Boolean);
    procedure TCipher.Decrypt(var Data; var DataSize: LongWord;
                      Last: Boolean);

The methods are designed for block ciphers but work with stream ciphers too. The Last argument defines whether the current portion of data is the last or not. For the last block the padding should be applied, and consequently the size of output data can differ from the size of input data. Generally the size of output data is larger for encryption and lesser for decryption; the difference can’t exceed the cipher’s block size. After the data is processed, the DataSize parameter contains the size of output data; the BufSize should be large enough to hold the output data, otherwise an exception is raised.


Stream ciphers expand a random key into a pseudorandom keystream and encrypt/decrypt by calculating xor of the keystream and the input data, no padding involved, so the size of output data is always equal to the size of input data. This operation is implemented by the method TCipher.KeyCrypt:

  procedure TCipher.KeyCrypt(var Data; DataSize: LongWord;
                             Last: Boolean);

which is the preferable method for encryption/decryption with a stream cipher.

The Last argument defines whether the current portion of data is last or not; if Last is false then the DataSize should be multiple of the cipher’s block size.

Legacy stream ciphers (RC4) have no block structure inside, so the “block size” for RC4 is equal to 1 (byte). On the other hand Salsa20 generates a keystream in 64-byte (that is 512-bit) blocks, sort of having a block cipher under the hood, so the notion of block size applies both to block and stream ciphers.


Any secure cipher can be used as a secure pseudorandom generator; the pseudorandom data can be generated by the method

  function TCipher.KeyStream(DataSize: LongWord): ByteArray;

The seed of the pseudorandom generator is a random key.


Block ciphers implement TCipher.KeyCrypt and TCipher.KeyStream methods by applying the CTR mode of operation without padding, which converts a block cipher into a stream cipher. Ex the right way to use the AES algorithm for generating pseudorandom integer values is to expand a random key for CTR mode without padding and call TCipher.KeyStream:

procedure RandDemo(const Key: ByteArray);
var
  Cipher: TCipher;
  I: Integer;
  Rand: LongWord;

begin
  Cipher:= Cipher.AES.ExpandKey(Key, CTR_ENCRYPT);
  for I:= 0 to 9 do begin
    Rand:= LongWord(Cipher.KeyStream(SizeOf(Rand)));
    Writeln(I:3, ': ', Rand);
  end;
end;

The RC5 block cipher algorithm is fully implemented as it was originally described, including 32- and 128-bit sized blocks. An instance of RC5 cipher can be created either as “standard” (8-byte block size, 12 rounds – just RC5) or “extended” (4-, 8- or 16-byte block size, 1..255 rounds – RC5(BlockSize, Rounds)):

procedure RC5BlockDemo(const Block, Key: ByteArray);
var
  CipherText, PlainText: ByteArray;

begin
  CipherText:= TCipher.RC5(Block.Len, 20)
                      .EncryptBlock(Block, Key);
  PlainText:= TCipher.RC5(Block.Len, 20)
                     .DecryptBlock(CipherText, Key);
  Assert(PlainText = Block);
end;

RC4 is a simple non-parallelizable stream cipher, widely used in today’s communication protocols but not recommended to use in new products because it is not considered secure now. Here is an example of file encryption/decryption using RC4:

procedure RC4FileDemo(const FileName: string; const Key: ByteArray);
begin
  TCipher.RC4.ExpandKey(Key)
             .Skip(1536)
             .EncryptFile(FileName, FileName + '.rc4');
  TCipher.RC4.ExpandKey(Key)
             .Skip(1536)
             .DecryptFile(FileName + '.rc4', FileName + '.bak');

The example uses TCipher.Skip method to discard the first 1536 bytes of RC4 keystream [recommended for security reasons in RFC4345] prior to encryption/decryption. The parameter of TCipher.Skip method is the number of cipher blocks to be discarded; since RC4 has no block structure the “block” of RC4 is 1 byte.


Salsa20 is one of the eStream portfolio stream ciphers, modern, fast and parallelizable. The instances of Salsa20 can be created as “standard” (20-rounds) or “non-standard” (any even number of rounds from 2 to 254):

    class function TCipher.Salsa20: TCipher;
    class function TCipher.Salsa20(Rounds: LongWord): TCipher;

I will tell more about Salsa20 support in the next post dedicated to multithreading with TCiphers.

Definitions of semantic security

0
  1. One-time semantic security.
  2. The simplest definition of semantic security is one-time semantic security which naturally applies to stream ciphers:

    An adversary sends two plaintext messages of equal length to the challenger and receives one encrypted message; semantic security means an adversary can’t distinguish which plaintext message was encrypted.

    The above is more an intuition than a definition; the strict formal definition involves details not suitable here.

    In practice a semantically secure stream cipher is as good as perfect one-time pad.

    The block cipher’s electronic codebook (ECB) mode of operation is not one-time semantically secure; the reason is ECB mode always maps identical plaintexts to identical ciphertexts. To win the game an adversary creates two messages of two blocks length; the first message consists of two identical blocks and the second consists of two different blocks; after receiving the ciphertext an adversary checks whether the ciphertext blocks are identical or not and decides which plaintext was encrypted. On the other hand the cipher block chaining (CBC) mode is one-time semantically secure.

  3. Semantic security under the chosen plaintext attack (CPA).
  4. One-time semantic security is not good for block ciphers because the block ciphers usually use many-time keys, so we need many-time security definition:

    An adversary sends q pairs of plaintext messages to the challenger; the challenger encrypts either the first messages or the second messages and sends them to an adversary; semantic security means an adversary can’t distinguish which messages (first or second) were encrypted.

    The above semantic security under CPA definition gives more power to an adversary. The CBC mode is semantically secure under CPA only if an initialization vector (IV) is unpredictable (random). If an adversary can predict the next IV used by the challenger he can create a one-block message which he can encrypt himself and use this message to win the CPA game.

    The semantic security under CPA implies that an adversary can force the challenger to encrypt the messages of his choice; all an adversary has to do is to send a pair of identical messages to the challenger and receive the ciphertext.

    So in the CPA game an adversary can get q-1 encrypted messages of his choice, then send the last q-th pair of different messages, receive the ciphertext and his goal now is to decide which message was encrypted.

  5. Semantic security under the chosen ciphertext attack (CCA).
  6. CCA game gives even more power to an adversary. Now an adversary can send queries of two types to the challenger – first type are the same pairs of plaintext messages as in the CPA game and the second type queries are ciphertexts which the challenger decrypts and sends the decrypted plaintexts back to an adversary. The adversary goal is to decide which plaintext messages, first or second, were encrypted in the queries of the first type.
    The only limitation is that an adversary can’t send ciphertexts which he receives from the challenger in the first type queries because otherwise the game is senseless.

    In the CCA game an adversary can force the challenger both to encrypt the plaintexts of his choice and decrypt ciphertexts of his choice; his goal again is to distinguish between the plaintext messages and decide which messages were encrypted.

    The CCA security is required against an active adversary, who can not only eavesdrop but also tamper, for example by blocking or injecting network packets. The CBC mode with random IV is not semantically secure under CCA. To be secure under CCA a system should provide CPA secure encryption with message authentication; the examples are SSL and IPSec protocols.