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).

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.

Endianness issue

2

TForge 0.68 is released.

TForge 0.68 is a maintenance release which fixes memory leak in THMAC implementation, fixes endianness issue for non-crypto hash functions such as CRC32 and adds minor improvements to ByteArray type.


Previous releases were returning message digest values for non-crypto hash functions in reversed byte order; the reasoning behind this design was that such function are returning integer values, and on little-endian CPU the byte order is reversed; this is not an issue anymore.

Since version 0.68 all hash functions return message digests in big-endian format, so there is no need to reverse byte order for non-crypto functions. This design is more consistent and also follows “least surprise” rule. When a non-crypto message digest is converted to integer type on a little-endian CPU the byte order is reversed under the hood.

TForge also contains alternative simpler and faster implementations of non-crypto functions in tfUtils.pas unit (TCRC32 and TJenkins1 types) which return message digests as an integer type and thus have no endianness dilemma at all.


Whenever a ByteArray method treats an instance data as an integer, it now assumes big-endian format. The examples are 2 new methods added in ver 0.68 – ByteArray.Incr and ByteArray.Decr. As names suggest the first method increments an instance data, the second decrements; both assumes that the data is an unsigned integer in big-endian format.

ByteArray.Incr method is useful for implementing some crypto primitives such as CTR mode of operation for block ciphers.


Happy New Year!

Dabbling in BASM

7

TForge 0.67 adds SHA-256 algorithm BASM optimization (applies also to SHA-224 which is based on SHA-256). Now the library contains BASM-optimized implementations of MD5, SHA1, SHA224 and SHA256 algorithms for Win32 and Win64 platforms.

Here are some benchmarks; I measured the time required to hash 500 MB of data on my laptop (Win7 64-bits, Intel Core i3 CPU) in milliseconds. Both Pascal and BASM implementations use fully unrolled compression routines. I used default compiler settings.

32-bit compiler (Delphi XE):

Delphi-pascal

Delphi-basm

64-bit compiler (FPC 2.6.2):

fpc64-pascal

fpc64-basm

High Performance Hash Library

1

TForge 0.66 released.

What’s new:

1. More hash algorithms added:

  • SHA224
  • SHA384
  • SHA512

2. MD5 and SHA1 compression routines were rewritten in BASM for CPUX86-WIN32 and CPUX64-WIN64 platforms and times faster now compared to pure pascal code (about 4 times for 32-bit compiler (Delphi XE) and about 3 times for 64-bit compiler (FPC 2.6.2) on my system).

3. Memory allocation bug in HMAC implementation was fixed.

On the Pointers and References

6

A Reference is a distinct concept in C/C++ languages. The next code sample (MinGW GCC compiler was used)

#include <iostream>

int main()
  {
    int Value;
    int &ValueRef = Value;

    Value = 2;
    std::cout << "Value: " << Value << "\n";
    std::cout << "ValueRef: " << ValueRef << "\n";

    ValueRef = 3;
    std::cout << "Value: " << Value << "\n";
    std::cout << "ValueRef: " << ValueRef << "\n";
    return 0;
  }

declares ValueRef as a reference to Value variable. The output is
_ref1
Though ValueRef variable is a pointer to Value internally the indirection operator is never used, and the syntax for accessing Value directly or indirectly via ValueRef is the same. ValueRef is also called an alias to Value; the point that ValueRef variable is a pointer internally is just an implementation detail.

Another important thing about C/C++ references is that they are always initialized. The language syntax enforces that you cannot declare a wild reference.

Pascal does not have the same reference concept. The closest concept is a procedure parameter passed by reference:

program ref;

{$APPTYPE CONSOLE}

var
  Value: Integer;

procedure Test(var ValueRef: Integer);
begin
  Writeln('ValueRef: ', ValueRef);
  ValueRef:= 3;
end;

begin
  Value:= 2;
  Writeln('Value: ', Value);
  Test(Value);

  Writeln('Value: ', Value);
  Test(Value);
end.

we can see that

  • ValueRef does not use indirection operator to access a referenced variable;
  • the language syntax enforces that ValueRef is always initialized.

Delphi does not elaborate the reference concept, though there are many built-in types in the language that are ‘transparent pointers’ – objects, interfaces, dynamic arrays, strings. The term reference can be used for example for object variables because the language syntax makes these variables indistinguishable from referenced instances. Instead the term object is usually used, that can mean object reference or object instance, so sometimes you think twice to understand what a particular object does mean.