From 2a6f5f10cc9713230bdd6204c57219451584f4a4 Mon Sep 17 00:00:00 2001 From: Jack Lloyd Date: Tue, 22 Sep 2015 12:10:24 -0400 Subject: McEliece cleanups Remove and consolidate various headers Reduce memory usage of GF2m_Field by sharing the log and exponent tables across all instances of a particular word size. Remove McEliece_Public_Operation and McEliece_Private_Operation which were difficult to use safely. Instead only the KEM operations are exposed. Add McEliece_PublicKey::random_plaintext_element Add command line `mce` tool and some McEliece documentation Convert the speed program to check McEliece keys of the suggested size Add McEliece KATs for both key generation and KEM Fix HMAC_DRBG constructor which derefed a pointer before its time --- doc/manual/contents.rst | 1 + doc/manual/mceliece.rst | 74 +++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 75 insertions(+) create mode 100644 doc/manual/mceliece.rst (limited to 'doc') diff --git a/doc/manual/contents.rst b/doc/manual/contents.rst index b0bc04e57..f69b7d77e 100644 --- a/doc/manual/contents.rst +++ b/doc/manual/contents.rst @@ -12,6 +12,7 @@ Contents rng filters pubkey + mceliece x509 ocsp tls diff --git a/doc/manual/mceliece.rst b/doc/manual/mceliece.rst new file mode 100644 index 000000000..51fa084e7 --- /dev/null +++ b/doc/manual/mceliece.rst @@ -0,0 +1,74 @@ +McEliece +======================================== + +McEliece is a cryptographic scheme based on error correcting codes which is +thought to be resistent to quantum computers. First proposed in 1978, it is fast +and patent-free. Variants have been proposed and broken, but with suitable +parameters the original scheme remains secure. However the public keys are quite +large, which has hindered deployment in the past. + +The implementation of McEliece in Botan was contributed by cryptosource GmbH. It +is based on the implementation HyMES, with the kind permission of Nicolas +Sendrier and INRIA to release a C++ adaption of their original C code under the +Botan license. It was then modified by Falko Strenzke to add side channel and +fault attack countermeasures. You can read more about the implementation at +http://www.cryptosource.de/docs/mceliece_in_botan.pdf + +Encryption in the McEliece scheme consists of choosing a message block of size +`n`, encoding it in the error correcting code which is the public key, then +adding `t` bit errors. The code is created such that knowing only the public +key, decoding `t` errors is intractible, but with the additional knowledge of +the secret structure of the code a fast decoding technique exists. + +The McEliece implementation in HyMES, and also in Botan, uses an optimization to +reduce the public key size, by converting the public key into a systemic code. +This means a portion of the public key is a identity matrix, and can be excluded +from the published public key. However it also means that in McEliece the +plaintext is represented directly in the ciphertext, with only a small number of +bit errors. Thus it is absolutely essential to only use McEliece with a CCA2 +secure scheme. + +One such scheme, KEM, is provided in Botan currently. It it a somewhat unusual +scheme in that it outputs two values, a symmetric key for use with an AEAD, and +an encrypted key. It does this by choosing a random plaintext (n - log2(n)*t +bits) using ``McEliece_PublicKey::random_plaintext_element``. Then a random +error mask is chosen and the message is coded and masked. The symmetric key is +SHA-512(plaintext || error_mask). As long as the resulting key is used with a +secure AEAD scheme (which can be used for transporting arbitrary amounts of +data), CCA2 security is provided. + +In ``mcies.h`` there are functions for this combination: + +.. cpp:function:: secure_vector mceies_encrypt(const McEliece_PublicKey& pubkey, \ + const secure_vector& pt, \ + byte ad[], size_t ad_len, \ + RandomNumberGenerator& rng, \ + const std::string& aead = "AES-256/OCB") + +.. cpp:function:: secure_vector mceies_decrypt(const McEliece_PrivateKey& privkey, \ + const secure_vector& ct, \ + byte ad[], size_t ad_len, \ + const std::string& aead = "AES-256/OCB") + +For a given security level (SL) a McEliece key would use +parameters n and t, and have the cooresponding key sizes listed: + ++-----+------+-----+--------------------------------+ +| SL | n | t | public key KB | private key KB | ++=====+======+=====+===============+================+ +| 80 | 1632 | 33 | 59 | 140 | ++-----+------+-----+---------------+----------------+ +| 107 | 2280 | 45 | 128 | 300 | ++-----+------+-----+---------------+----------------+ +| 128 | 2960 | 57 | 195 | 459 | ++-----+------+-----+---------------+----------------+ +| 147 | 3408 | 67 | 265 | 622 | ++-----+------+-----+---------------+----------------+ +| 191 | 4624 | 95 | 516 | 1234 | ++-----+------+-----+---------------+----------------+ +| 256 | 6624 | 115 | 942 | 2184 | ++-----+------+-----+---------------+----------------+ + +You can check the speed of McEliece with the suggested parameters above +using ``botan speed McEliece``, and can encrypt files using the ``botan mce`` +command. -- cgit v1.2.3