Kalyna

From Crypto++ Wiki
Jump to: navigation, search
Kalyna
Documentation
#include <cryptopp/kalyna.h>

Kalyna is a Ukrainian block cipher designed by Roman Oliynykov, Ivan Gorbenko, Oleksandr Kazymyrov, Victor Ruzhentsev, Oleksandr Kuznetsov, Yurii Gorbenko, Oleksandr Dyrda, Viktor Dolgov, Andrii Pushkaryov, Ruslan Mordvinov, Dmytro Kaidalov that features a modern design comparable to AES. The keys and block sizes range from 128-bits to 512-bits, and the cipher performs above average on modern 64-bit hardware. The paper which introduces the cipher can be found at A New Encryption Standard of Ukraine: The Kalyna Block Cipher.

Crypto++ added the block cipher at Commit a5c67cfdd6ad (the big-endian port occurred at Commit 1d7dfc69274d). Kalyna is the library's first attempt to support variable size block ciphers, so things may change after this writing. Generally speaking Kalyna is a lot like a fixed size block cipher. However, key lengths and block sizes are coupled or paired, so you have to be mindful if you want sizes other than the defaults.

As of this writing there are several open tasks for large block ciphers. The last prominent issue is, what to do with GCM mode. NIST only approves AES for GCM, so larger polynomials are missing for block sizes of 256-bit, 512-bit and 1024-bit. We believe we have the correct polynomials, but we need to modify GCM. Also Issue 423, Polynomials for CMAC and GCM mode.

Note: if your project is using encryption alone to secure your data, encryption alone is usually not enough. Please take a moment to read Authenticated Encryption and understand why you should prefer to use CCM, GCM, or EAX over other modes, such as CBC or CTR.

Algorithm Name

If you call StaticAlgorithmName then the function will return the generic "Kalyna". StaticAlgorithmName always returns the base name and keying does not affect it. If you call AlgorithmName on an object that has not been keyed then you will get the same result.

Once you key the cipher you will receive a result similar to the following program. The name follows DSTU 7624:2014, where block size is provided first and then key length. The library uses a dash to identify block size and parenthesis to identify key length. For example, Kalyna-128(256) is Kalyna with a 128-bit block size and a 256-bit key length. If a mode is associated with the object, then it follows as expected. For example, Kalyna-256(512)/ECB denotes Kalyna with a 256-bit block and 512-bit key operated in ECB mode.

int main(int argc, char* argv[])
{
    Kalyna::Encryption kalyna;
    
    cout << "StaticAlgorithmName: " << kalyna.StaticAlgorithmName() << endl;
    cout << "AlgorithmName (unkeyed): " << kalyna.AlgorithmName() << endl;

    byte key[Kalyna::DEFAULT_KEYLENGTH];
    kalyna.SetKey(key, sizeof(key));

    cout << "AlgorithmName (keyed): " << kalyna.AlgorithmName() << endl;
    
    return 0;
}

The program results in the following output.

$ ./test.exe
StaticAlgorithmName: Kalyna
AlgorithmName (unkeyed): Kalyna
AlgorithmName (keyed): Kalyna-128(128)

Modes of Operation

Kalyna is considered a "wide block" block cipher because it uses block sizes greater than 128-bits. There are pain points when using wide block ciphers, like incomplete support for some modes of operation. The problem is largely due to missing specifications for the wider block sizes, which means we don't know how to implement an algorithm in a standard way. A side effect is, no specifications lead to missing test vectors.

Examples of missing specifications include missing polynomials for CMAC and GCM modes of operation. It is not enough to simply use a low weight polynomial since there can be multiple primitive polynomials available. We are tracking the missing polynomials at Issue 423, Polynomials for CMAC and GCM mode.

Another example of a missing specification is counter mode operations. The mode could be as simple as using a larger counter, or it could use a zero-extended 128-bit counter. Sometimes the result of counter mode operation is reduced by a primitive polynomial, so it can also suffer missing polynomials detailed in CMAC and GCM.

Yet another example is CCM, EAX and GCM are authenticated encryption modes of operation. The modes produce an authentication tag and the tag has traditionally been the size of the block. In the case of AES, Camellia that's 128-bits and it is sufficient to authenticate the data. In the case of wide blocks we don't know if tags should be extended accordingly. As we understand the latest revision to OCB mode, the tags are not extended.

At this point in time we believe the status of wide block modes of operation are:

  • CMAC - may work, but we don't have test vectors
  • CBC - probably works, we had Kalyna test vectors
  • CTR - probably works, we had Kalyna test vectors
  • EAX - may work, but we don't have test vectors
  • GCM - does not work, we don't have an implementation
  • CCM - probably does not work, we don't have a specification
  • OCB - in progress, not ready for production
  • Others - modes like OFB and CFB probably work

In a few places we said, "probably works, we had Kalyna test vectors". There is a danger we cannot make the leap because Kalyna uses operations specified in DSTU, which is a Ukranian national standard. The standard may be different than what ISO/IEC, NESSIE, NIST or the IETF eventually produce.

BlockSize

Variable block sizes introduced the need for DEFAULT_BLOCKSIZE. DEFAULT_BLOCKSIZE is to VariableBlockSize as DEFAULT_KEYLENGTH is to VariableKeyLength. It provides a sane default in a generic way. For Kalyna, DEFAULT_BLOCKSIZE is 16 bytes or 128-bits; and its paired or couple to a DEFAULT_KEYLENGTH of 16 bytes or 128-bits. If you do nothing special, the the default cipher is Kalyna-128(128).

When inheriting from VariableBlockSize, there is also a MIN_BLOCKSIZE and MAX_BLOCKSIZE just like with VariableKeyLength. For Kalyna, the range is 16-bytes to 64-bytes.

Sample Programs

There are four sample programs below. The first prints key and block size for the cipher. Its mostly boring.

The second sample uses Kalyna like a fixed size block cipher and things "just work" with the default values from DEFAULT_KEYLENGTH and DEFAULT_BLOCKSIZE. The default values are a 128-bit key and a 128-bit block size. It also uses a StreamTransformationFilter to handle buffering and padding.

The third and fourth program are the interesting ones. The first uses a 512-bit key and a 256-bit blocksize, and the second uses a 512-bit key and a 512-bit blocksize. They demonstrates some the things you must do differently when using the larger blocksizes.

Key and Block sizes

Below is the first program. It prints key and block size for the cipher.

int main(int argc, char* argv[])
{
    cout << "Default keylength: " << Kalyna::DEFAULT_KEYLENGTH << endl;
    cout << "Minimum keylength: " << Kalyna::MIN_KEYLENGTH << endl;
    cout << "Maximum keylength: " << Kalyna::MAX_KEYLENGTH << endl;
	
    cout << "Default blocksize: " << Kalyna::DEFAULT_BLOCKSIZE << endl;
    cout << "Minimum blocksize: " << Kalyna::MIN_BLOCKSIZE << endl;
    cout << "Maximum blocksize: " << Kalyna::MAX_BLOCKSIZE << endl;

    return 0;
}

Running the program results in a range of 16 to 64 bytes.

$ ./test.exe
Default keylength: 16
Minimum keylength: 16
Maximum keylength: 64

Default blocksize: 16
Minimum blocksize: 16
Maximum blocksize: 64

128-bit key, 128-bit block

The second program uses Kalyna like a fixed size block cipher and things "just work" with the default values from DEFAULT_KEYLENGTH and DEFAULT_BLOCKSIZE. The default values are a 128-bit key and a 128-bit block size. It also uses a StreamTransformationFilter to handle buffering and padding.

The second program uses the Kaylna-128(128)/CBC/NoPadding test vector provided by DSTU 7624:2014. The test vectors can be found at TestVectors/kalyna.txt. Roman Oliynykov was kind enough to translate the relevant section from the DSTU document and send the pages to us for use in the library.

int main(int argc, char* argv[])
{
    byte key[] = "\x00\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0A\x0B\x0C\x0D\x0E\x0F";
    byte iv[] = "\x10\x11\x12\x13\x14\x15\x16\x17\x18\x19\x1A\x1B\x1C\x1D\x1E\x1F";

    CBC_Mode<Kalyna>::Encryption kalyna;
    kalyna.SetKeyWithIV(key, 16, iv, 16);
    
    byte plain[] = "\x20\x21\x22\x23\x24\x25\x26\x27\x28\x29\x2A\x2B\x2C\x2D\x2E\x2F"
        "\x30\x31\x32\x33\x34\x35\x36\x37\x38\x39\x3A\x3B\x3C\x3D\x3E\x3F"
        "\x40\x41\x42\x43\x44\x45\x46\x47\x48\x49\x4A\x4B\x4C\x4D\x4E\x4F";        

    BlockPaddingSchemeDef::BlockPaddingScheme padding = BlockPaddingSchemeDef::NO_PADDING;
    StreamTransformationFilter encryptor(kalyna, new HexEncoder(new FileSink(cout)), padding);
    
    cout << "Cipher text: ";
    encryptor.Put(plain, 48);
    encryptor.MessageEnd();
    cout << endl;
    
    return 0;
}

Running the program results in the expected output.

$ ./test.exe
Cipher text: A73625D7BE994E85469A9FAABCEDAAB6DBC5F65DD77BB35E06BD7D1D8EAFC86
24D6CB31CE189C82B8979F2936DE9BF14

You can also use the classic one-liner:

StringSource(plain, 48, new StreamTransformationFilter(kalyna, new HexEncoder(new FileSink(cout))));

512-bit key, 256-bit block

The third program uses Kalyna-256 with a 512-bit key in CBC mode. The test vectors can be found at TestVectors/kalyna.txt.

The third example is the interesting case because it demonstrates how to change the block size. To change the block size, you have to use an AlgorithmParameters object and provide parameters for BlockSize() and IV(). The reason why is discussed at SetKeyWithBlockSizeAndIV.

int main(int argc, char* argv[])
{
    byte key[] = "\x00\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0A\x0B\x0C\x0D\x0E\x0F"
        "\x10\x11\x12\x13\x14\x15\x16\x17\x18\x19\x1A\x1B\x1C\x1D\x1E\x1F"
        "\x20\x21\x22\x23\x24\x25\x26\x27\x28\x29\x2A\x2B\x2C\x2D\x2E\x2F"
        "\x30\x31\x32\x33\x34\x35\x36\x37\x38\x39\x3A\x3B\x3C\x3D\x3E\x3F";

    byte iv[] = "\x40\x41\x42\x43\x44\x45\x46\x47\x48\x49\x4A\x4B\x4C\x4D\x4E\x4F"
        "\x50\x51\x52\x53\x54\x55\x56\x57\x58\x59\x5A\x5B\x5C\x5D\x5E\x5F";

    AlgorithmParameters params = MakeParameters(Name::BlockSize(), 32)
        (Name::IV(), ConstByteArrayParameter((const byte *)iv, 32));

    CBC_Mode<Kalyna>::Encryption kalyna;
    kalyna.SetKey(key, 64, params);
    
    byte plain[] = "\x60\x61\x62\x63\x64\x65\x66\x67\x68\x69\x6A\x6B\x6C\x6D\x6E\x6F"
        "\x70\x71\x72\x73\x74\x75\x76\x77\x78\x79\x7A\x7B\x7C\x7D\x7E\x7F"
        "\x80\x81\x82\x83\x84\x85\x86\x87\x88\x89\x8A\x8B\x8C\x8D\x8E\x8F"
        "\x90\x91\x92\x93\x94\x95\x96\x97\x98\x99\x9A\x9B\x9C\x9D\x9E\x9F"
        "\xA0\xA1\xA2\xA3\xA4\xA5\xA6\xA7\xA8\xA9\xAA\xAB\xAC\xAD\xAE\xAF"
        "\xB0\xB1\xB2\xB3\xB4\xB5\xB6\xB7\xB8\xB9\xBA\xBB\xBC\xBD\xBE\xBF";

    BlockPaddingSchemeDef::BlockPaddingScheme padding = BlockPaddingSchemeDef::NO_PADDING;
    StreamTransformationFilter encryptor(kalyna, new HexEncoder(new FileSink(cout)), padding);
    
    cout << "Cipher text: ";
    encryptor.Put(plain, 96);
    encryptor.MessageEnd();
    cout << endl;
    
    return 0;
}

Running the program produces the expected result:

$ ./test.exe
Cipher text: B8A2474578C2FEBF3F94703587BD5FDC3F4A4D2F43575B6144A1E1031FB3D14
52B7FD52F5E3411461DAC506869FF8D2FAEF4FEE60379AE00B33AA3EAF911645AF8091CD8A45
D141D1FB150E5A01C1F26FF3DBD26AC4225EC7577B2CE57A5B0FF

If you want to use Kalyna-512(512) then the code would change as follows.

AlgorithmParameters params = MakeParameters(Name::BlockSize(), 64)
    (Name::IV(), ConstByteArrayParameter((const byte *)iv, 64));

CBC_Mode<Kalyna>::Encryption kalyna;
kalyna.SetKey(key, 64, params);

512-bit key, 512-bit block

The final program uses Kalyna-512with a 512-bit key in CBC mode. The test vectors can be found at TestVectors/kalyna.txt.

int main(int argc, char* argv[])
{
    const byte key[] = "\x00\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0A\x0B\x0C\x0D\x0E\x0F"
        "\x10\x11\x12\x13\x14\x15\x16\x17\x18\x19\x1A\x1B\x1C\x1D\x1E\x1F"
        "\x20\x21\x22\x23\x24\x25\x26\x27\x28\x29\x2A\x2B\x2C\x2D\x2E\x2F"
        "\x30\x31\x32\x33\x34\x35\x36\x37\x38\x39\x3A\x3B\x3C\x3D\x3E\x3F";

    const byte iv[] = "\x40\x41\x42\x43\x44\x45\x46\x47\x48\x49\x4A\x4B\x4C\x4D\x4E\x4F"
        "\x50\x51\x52\x53\x54\x55\x56\x57\x58\x59\x5A\x5B\x5C\x5D\x5E\x5F"
        "\x60\x61\x62\x63\x64\x65\x66\x67\x68\x69\x6A\x6B\x6C\x6D\x6E\x6F"
        "\x70\x71\x72\x73\x74\x75\x76\x77\x78\x79\x7A\x7B\x7C\x7D\x7E\x7F";

    AlgorithmParameters params = MakeParameters(Name::BlockSize(), 64)
        (Name::IV(), ConstByteArrayParameter((const byte *)iv, 64));

    CBC_Mode<Kalyna>::Encryption kalyna;
    kalyna.SetKey(key, 64, params);
    
    const byte plain[] = "\x80\x81\x82\x83\x84\x85\x86\x87\x88\x89\x8A\x8B\x8C\x8D\x8E\x8F"
        "\x90\x91\x92\x93\x94\x95\x96\x97\x98\x99\x9A\x9B\x9C\x9D\x9E\x9F"
        "\xA0\xA1\xA2\xA3\xA4\xA5\xA6\xA7\xA8\xA9\xAA\xAB\xAC\xAD\xAE\xAF"
        "\xB0\xB1\xB2\xB3\xB4\xB5\xB6\xB7\xB8\xB9\xBA\xBB\xBC\xBD\xBE\xBF"
        "\xC0\xC1\xC2\xC3\xC4\xC5\xC6\xC7\xC8\xC9\xCA\xCB\xCC\xCD\xCE\xCF"
        "\xD0\xD1\xD2\xD3\xD4\xD5\xD6\xD7\xD8\xD9\xDA\xDB\xDC\xDD\xDE\xDF"
        "\xE0\xE1\xE2\xE3\xE4\xE5\xE6\xE7\xE8\xE9\xEA\xEB\xEC\xED\xEE\xEF"
        "\xF0\xF1\xF2\xF3\xF4\xF5\xF6\xF7\xF8\xF9\xFA\xFB\xFC\xFD\xFE\xFF";

    const BlockPaddingSchemeDef::BlockPaddingScheme padding = BlockPaddingSchemeDef::NO_PADDING;
    StreamTransformationFilter encryptor(kalyna, new HexEncoder(new FileSink(cout)), padding);
    
    cout << "Cipher text: ";
    encryptor.Put(plain, 128);
    encryptor.MessageEnd();
    cout << endl;
    
    return 0;
}

Running the program results in the following.

$ ./test.exe
Cipher text: D4739B829EF901B24C1162AE4FDEF897EDA41FAC7F5770CDC90E1D1CDF124E8
D7831E06B4498A4B6F6EC815DF2461DC99BB0449B0F09FCAA2C84090534BCC9329626FD74EF8
F0A0BCB5765184629C3CBF53B0FB134F6D0421174B1C4E884D1CD1069A7AD19752DCEBF65584
2E79B7858BDE01390A760D85E88925BFE38B0FA57

Authenticated Encryption

This section discusses the use of Authenticated Encryption modes of operation like CCM, EAX and GCM. Using the modes is usually slightly different from the more traditional modes like ECB and CBC. However, the wider block sizes and polynomials are adding twists so there are some rough edges.

GCM Mode

Earlier we said we were not sure what to do with GCM because the mode uses polynomials during multiplication, and NIST only specifies a 16-byte block size to be used with AES. The Kalyna team was kind enough to provide polynomials for all the block sizes, and they are listed below. They appear to be the same polynomials from Table of Low-Weight Binary Irreducible Polynomials.

  • 128-bit block: x127 + x7 + x2 + x + 1
  • 256-bit block: x256 + x10 + x5 + x + 1
  • 512-bit block: x512 + x8 + x5 + x2 + 1

Support for the larger block sizes and polynomials has not been added yet. Attempting to operate Kalyna-512(512) in GCM mode results in an exception.

$ ./test.exe
Kalyna-512(512)/GCM: block size of underlying block cipher is not 16

EAX Mode

EAX mode is similar to GCM mode. EAX relies upon CMAC, and CMAC requires the use of a polynomial during GF multiplication. EAX mode is somewhat unique because it already had support for 256-bit block size. Commit e226523b05b5d6ab and commit 7697857481f51c51 added support for the 512-bit block size.

Below is an example of using EAX mode with Kalyna. The parameters, like key and iv, were taken from Kalyna-512(512) in CBC mode. The problem is, we are not sure if CMAC mode was correctly modified, or if the result below is expected because we don't have a test vector.

int main(int argc, char* argv[])
{
    const byte key[] = "\x00\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0A\x0B\x0C\x0D\x0E\x0F"
        "\x10\x11\x12\x13\x14\x15\x16\x17\x18\x19\x1A\x1B\x1C\x1D\x1E\x1F"
        "\x20\x21\x22\x23\x24\x25\x26\x27\x28\x29\x2A\x2B\x2C\x2D\x2E\x2F"
        "\x30\x31\x32\x33\x34\x35\x36\x37\x38\x39\x3A\x3B\x3C\x3D\x3E\x3F";

    const byte iv[] = "\x40\x41\x42\x43\x44\x45\x46\x47\x48\x49\x4A\x4B\x4C\x4D\x4E\x4F"
        "\x50\x51\x52\x53\x54\x55\x56\x57\x58\x59\x5A\x5B\x5C\x5D\x5E\x5F"
        "\x60\x61\x62\x63\x64\x65\x66\x67\x68\x69\x6A\x6B\x6C\x6D\x6E\x6F"
        "\x70\x71\x72\x73\x74\x75\x76\x77\x78\x79\x7A\x7B\x7C\x7D\x7E\x7F";

    AlgorithmParameters params = MakeParameters(Name::BlockSize(), 64)
        (Name::IV(), ConstByteArrayParameter((const byte *)iv, 64));

    EAX<Kalyna>::Encryption kalyna;
    kalyna.SetKey(key, 64, params);
    
    const byte plain[] = "\x80\x81\x82\x83\x84\x85\x86\x87\x88\x89\x8A\x8B\x8C\x8D\x8E\x8F"
        "\x90\x91\x92\x93\x94\x95\x96\x97\x98\x99\x9A\x9B\x9C\x9D\x9E\x9F"
        "\xA0\xA1\xA2\xA3\xA4\xA5\xA6\xA7\xA8\xA9\xAA\xAB\xAC\xAD\xAE\xAF"
        "\xB0\xB1\xB2\xB3\xB4\xB5\xB6\xB7\xB8\xB9\xBA\xBB\xBC\xBD\xBE\xBF"
        "\xC0\xC1\xC2\xC3\xC4\xC5\xC6\xC7\xC8\xC9\xCA\xCB\xCC\xCD\xCE\xCF"
        "\xD0\xD1\xD2\xD3\xD4\xD5\xD6\xD7\xD8\xD9\xDA\xDB\xDC\xDD\xDE\xDF"
        "\xE0\xE1\xE2\xE3\xE4\xE5\xE6\xE7\xE8\xE9\xEA\xEB\xEC\xED\xEE\xEF"
        "\xF0\xF1\xF2\xF3\xF4\xF5\xF6\xF7\xF8\xF9\xFA\xFB\xFC\xFD\xFE\xFF";

    // NO_PADDING is default for EAX
    AuthenticatedEncryptionFilter encryptor(kalyna, new HexEncoder(new FileSink(cout)));
    
    cout << "Cipher text: ";
    encryptor.Put(plain, 128);
    encryptor.MessageEnd();
    cout << endl;
    
    return 0;
}

Running the program results in the following.

$ ./test.exe
Cipher text: 284ECCD2A00A70CF6D48669C8FF56122CA66000B99DB77208FC381A604502C3
4BA1B4AB6C2D0EB04BBD03D7A2922C0F5A497C55ADA813C7A0FEE65CCADE08A5C7C10F866980
FC8C3029EC3CF2062C390322B009E4C77A685764D253B4EC2DE44569B02462171C2691F20CC1
AC43747316868C517BEF06C32C99B39838EB77E1D03235097F58164FA9AA679AE6115140B8DE
EAD98D7E09CEDD2F0D9F2E888B7B200E77CDD76144AF3ADFAC2FEB6A98B50DB9BEB6C7CE2F7D
1CCBE6E36A5B2BDEF

SetKeyWithBlockSizeAndIV

We could add an additional class method to SimpleKeyingInterface like SetKeyWithBlockSizeAndIV to handle an different blocksizes. For example, we could do the following, which is similar to SetKeyWithIV.

SetKeyWithBlockSizeAndIV(const byte *key, size_t length,
        unsigned int blocksize, const byte *iv, size_t ivLength)
{
    this->SetKey(key, length,  MakeParameters(Name::BlockSize(), blocksize)
        (Name::IV(), ConstByteArrayParameter((const byte *)iv, ivLength));
}

The problem is, the method does not make sense for SimpleKeyingInterface. The method would be added to all classes which inherit from the interface, including block ciphers, hashes and message authentication codes. Nearly all block ciphers, hashes and authentication codes do not have a notion of a variable block size.

Maybe the method would make better sense in a new class, like VariableBlockSizeImpl. Or maybe the recently added VariableBlockCipher interface and VariableBlockCipherImpl class.

Downloads

Kalyna-CBC-Filter.zip - Demonstrates encryption and decryption using Kalyna in CBC mode with filters (confidentiality only)

Kalyna-Test-Vectors.zip - Kalyna test vectors for CBC and CTR mode from DSTU 7624:2014. The Kalyna team extracted the test vectors from the DSTU document. The ZIP also includes the email with the translations.