Cryptography Engineering

Niels Ferguson, Bruce Schneier, Tadayoshi Kohno

Mentioned 5

The ultimate guide to cryptography, updated from an author team of the world's top cryptography experts. Cryptography is vital to keeping information safe, in an era when the formula to do so becomes more and more challenging. Written by a team of world-renowned cryptography experts, this essential guide is the definitive introduction to all major areas of cryptography: message security, key negotiation, and key management. You'll learn how to think like a cryptographer. You'll discover techniques for building cryptography into products from the start and you'll examine the many technical changes in the field. After a basic overview of cryptography and what it means today, this indispensable resource covers such topics as block ciphers, block modes, hash functions, encryption modes, message authentication codes, implementation issues, negotiation protocols, and more. Helpful examples and hands-on exercises enhance your understanding of the multi-faceted field of cryptography. An author team of internationally recognized cryptography experts updates you on vital topics in the field of cryptography Shows you how to build cryptography into products from the start Examines updates and changes to cryptography Includes coverage on key servers, message security, authentication codes, new standards, block ciphers, message authentication codes, and more Cryptography Engineering gets you up to speed in the ever-evolving field of cryptography.

More on Amazon.com

Mentioned in questions and answers.

Since SSL is the backbone of the secure internet, (now technically called TLS), what are some good books I should read up on to understand all aspects of it?

I suppose I'll need to learn some math, some PKI books, crypto, and Sysadmin books as well. Since that isn't a complete list I'm interested in hearing what you think is wise to learn as well.

As far as cryptography goes, this is the best there is:

Applied Cryptography: Protocols, Algorithms, and Source Code in C

You will learn all there is from the basic building blocks upwards.

I only have some very rudimentary theoretical knowledge about RSA.

While reading different sources about how to use it in practice, it seemed that PKCS#1 OAEP would be a good thing.

For a test implementation, I use Python with PyCrypto. E.g. this is an example using PKCS#1 OAEP.

Encrypting using the public key and then decrypting using the private key works fine. E.g. the public can send some data to person X with the private key.

From my basic understanding of how RSA works, I thought that I can just interchange the public/private key, i.e. I can use the public key for encrypting and the private key for decrypting. E.g. person X can encrypt some data with its own private key and the public can decrypt it using the public key. If the decryption works fine, this gives some sort of proof that the data is coming from person X.

PyCrypto complains when I try to decrypt using the public key.

From reading the PyCrypto source code, in the _RSAKey._decrypt function (here), it seems that the key object itself knows if it is the private or public key and differs between them (to my surprise, again based on my very basic RSA understanding).

From there, it looks like I could hack the decrypt function so that it uses the public key. Or somewhat differently: I could just interchange the public exponent e and the private exponent d in the key objects.

But all this seems like it is not intended to be used/hacked this way. So I wanted to ask here about my misunderstandings.

Also, just out of curiosity, I generated some keys (RSA.generate(2048)) and looked at n, e and d. In all cases, n and d was very huge while e was in all cases constant (65537) (I wouldn't have expected that).

I guess from all this that I really shouldn't just interchange e and d.

So I guess I should use some other method for the signature like PKCS1_PSS.


Some code for the encrypting/decrypting, if anyone is interested:

def randomString(l):
    import random
    return ''.join(chr(random.randint(0, 0xFF)) for i in range(l))

def genkeypair():
    from Crypto.PublicKey import RSA
    key = RSA.generate(2048)
    pubkey = key.publickey().exportKey("DER")
    privkey = key.exportKey("DER")
    return (pubkey,privkey)

def encrypt(v, rsapubkey):
    from Crypto.PublicKey import RSA
    rsakey = RSA.importKey(rsapubkey)
    from Crypto.Cipher import PKCS1_OAEP
    rsa = PKCS1_OAEP.new(rsakey)
    import binstruct
    from array import array
    aeskey = randomString(32)
    iv = randomString(16)
    from Crypto.Cipher import AES
    aes = AES.new(aeskey, AES.MODE_CBC, iv)
    data = binstruct.varEncode(v)
    data += array("B", (0,) * (-len(data) % 16))
    out = binstruct.strEncode(rsa.encrypt(aeskey + iv))
    out += array("B", aes.encrypt(data))
    return out

def decrypt(stream, rsaprivkey):
    from array import array
    from StringIO import StringIO
    if isinstance(stream, array): stream = stream.tostring()
    if isinstance(stream, str): stream = StringIO(stream)
    from Crypto.PublicKey import RSA
    rsakey = RSA.importKey(rsaprivkey)
    from Crypto.Cipher import PKCS1_OAEP
    rsa = PKCS1_OAEP.new(rsakey)
    import binstruct
    aesdata = binstruct.strDecode(stream)
    aesdata = rsa.decrypt(aesdata)
    aeskey = aesdata[0:32]
    iv = aesdata[32:]
    from Crypto.Cipher import AES
    aes = AES.new(aeskey, AES.MODE_CBC, iv)
    class Stream:
        buffer = []
        def read1(self):
            if len(self.buffer) == 0:
                nextIn = stream.read(16)
                self.buffer += list(aes.decrypt(nextIn))
            return self.buffer.pop(0)
        def read(self, n):
            return "".join([self.read1() for i in range(n)])
    v = binstruct.varDecode(Stream())
    return v

(binstruct is a small module which can encode/decode tree data structures - similar to JSON/BSON.)

That is where I thought I could just also use encrypt with the private key and and decrypt with the public key.


The final implementation with (hopefully) correct signing/authentication can be found here in binstruct.

Your general understanding about interchanging the roles of public and private key is correct. In the end, RSA is based on the fact that

m^(ed) congruent m (mod n)

What is normally titled RSA encryption is typically the operation

m^e mod n,

raising the message to the e-th power where e is the public key.

Decryption is then

(m^e)^d mod n,

raising the encrypted message to the d-th power with d being the private key. Now because of the rules of exponentiation and the fact that multiplication is commutative (these still hold in modular arithmetic) we have that

m congruent (m^e)^d congruent m^(ed) congruent m^(de) congruent (m^d)^e,

and therefore you get the same result if you apply the operations in the reverse order.

You were right in assuming that the reversal leads to digital signatures, because everybody can verify ("decrypt") the signature with the public key e, so the message was authentic only if it was "encrypted" (signed) using the corresponding private key d.

As it turns out, PyCrypto is only trying to prevent you from mistaking one for the other here, OpenSSL or Ruby OpenSSL allow you for example to do both: public_encrypt/public_decrypt and private_encrypt/private_decrypt.

So much for the theory, now to why there is good reason for not letting you use them interchangeably. What I just described is often referred to as "textbook RSA" and it is still far from being secure. Additional things need to be taken care of to make the result usable in practice. And that's why there is a dedicated signature package in PyCrypto - this effectively does what you described, but also additionally takes care of the things I mentioned. While it is good for our understanding to know how these things work, we should always use such packages in practice because they already made and fixed the mistakes we would probably introduce when rolling our own.

As to why e is always 65537. It doesn't really have to be a fixed value, but it is commonly chosen to be a very small number with as few 1's in its binary representation as possible (65537 is 10001). In the past, e=3 or e=17 were also chosen, but were considered as not safe in practice because they could be attacked by simply taking the 3rd or 17th root of the ciphertext. If e=3 and m=3, then 3^3 is 27, and it takes no genius to figure out that m is 3 given that the ciphertext is 27, regardless of the modulus n (which is typically much larger). So the danger lies in the fact that the ciphertext, even after exponentiation, does not cross "the modulus boundary" and therefore allows us to simply take the e-th root to arrive at the original message. With typical moduli of 1024 - 4096 bits, this is no longer an issue with e=65537.

Few 1's in the binary representation are also good for computing m^e fast. Modular exponentiation is often implemented using a Multiply and Square algorithm, and performance is best for small e's with few 1's. Why is it chosen this way and not the other way round, for example having a small d with few 1's? Well for starters, d would be easier to guess that way. A second advantage is that with digital signatures, you typically sign a document once but verify it often. This means m^d is performed once but m^e often, so you have the common task perform best while the rare task is allowed to perform poor.

Edit:

You asked whether I could further explain what schemes like RSA-PSS do in order to be secure.

When comparing what OAEP does for encryption and what PSS does for signatures, the two look pretty similar. And in fact they are, they both introduce randomization in the process, which allows for provable security of OAEP and PSS under certain assumptions. I also found this paper to be helpful. Provable security is a big advantage over old-school PKCS 1.5 encryption and signatures, which can be shown to be not provably secure under the same assumptions (key point: no deterministic scheme can be, randomization is essential). An obvious difference between the proposed signature and encryption schemes is that the signature schemes always mandate the to-be-signed message to be hashed first. This makes sense not only with regard to efficiency, but it also prevents some attacks that would otherwise be possible. And I guess that leads to the gist of why we should always use signature schemes for signatures and encryption schemes for encryption: the proposed schemes come with security proofs attached, our handmade schemes don't.

Cryptographers invent those schemes to make the lives of us mere mortals easier - they give us tools that ideally allow for no abuse or misuse by reducing the number of options to a minimum. For example, even if you managed to come up with a good signature scheme using RSA-OAEP, somebody who uses it might not know about why they should hash their messages first before applying the signature. That kind of misuse is not even a possibility with RSA-PSS.

You also asked about some good reading material. Although this is a very subjective topic, I really enjoyed these:

The practical side:

  • Applied Cryptography - still a classic and worth reading. Some security people say it is dangerous because it leads people to believing they know enough to write their own crypto. But I guess we are all grown-ups, aren't we? It's still great to get a feeling about "what's out there"

  • Cryptography Engineering - Has some good practical advice and also mentions the caveats when implementing cryptography code.

  • Handbook of Applied Cryptography - It's free and still has a lot of good advice especially with regard to implementations.

The theoretical side:

  • Modern Cryptography - It's a hybrid between theory and practice and has a lot of insight how things can go wrong in practice.

  • Cryptography - Theory and Practice - this was a game changer for me, I love this book. If you only ever read one book, let it be this one :)

  • Introduction to Modern Cryptography - does a great job at explaining "the modern approach" and how the security proofs actually work and under which assumptions.

  • Foundations of Cryptography I&II - if after the previous book you still can't get enough of the theory of one-way functions and friends, this is your book. Very technical.

Security is not only cryptography:

  • Security engineering - has numerous examples how sound principles can go wrong in practice

  • Information Security - Similar to Security Engineering, illustrating security in a scope wider than just cryptography.

Apart from that, I try to keep up to date by reading recent papers about new attacks, technologies etc. I found r/netsec very helpful, as well as following researchers and practitioners on Twitter, they post interesting material regularly.

Finally, if you have the time, take the Cryptography courses on Coursera and Udacity! I think they'll start over in the next few weeks, they are really great, I'm sure you won't regret it. They had a lot of practical exercises that are a lot of fun and nicely illustrate various ways to attack cryptography implementations.

Which books are really MUST read for a person who attempts to create a critical parts of application(s) in security field, e.g. driver which are dealing with coding/decoding, firewall, kernel subsystem which rely on checking of rights/policies, a secure mail client, etc.

Are there any specific books covering applied C programming topics in field like this? Like how to design/write secure code, what are the common attacks your program must be resistant to and the like?

In my opinion, these are must-reads:

Cryptography in C and C++ - http://www.amazon.com/Cryptography-C-Michael-Welschenbach/dp/1590595025/

Secure Programming Cookbook for C and C++: Recipes for Cryptography, Authentication, Input Validation & More - http://www.amazon.com/Secure-Programming-Cookbook-Cryptography-Authentication/dp/0596003943/

Cryptography Engineering: Design Principles and Practical Applications - http://www.amazon.com/Cryptography-Engineering-Principles-Practical-Applications/dp/0470474246/

Security Metrics: Replacing Fear, Uncertainty, and Doubt - http://www.amazon.com/Security-Metrics-Replacing-Uncertainty-Doubt/dp/0321349989/

Security Engineering: A Guide to Building Dependable Distributed Systems - http://www.amazon.com/Security-Engineering-Building-Dependable-Distributed/dp/0470068523/ (High-level, management issues, etc.)

The following book deserves honorable mention, although many experts repudiate it these days. However, some say it is the best book on the subject, so judge for yourself:

Applied Cryptography: Protocols, Algorithms, and Source Code in C, Second Edition - http://www.amazon.com/Applied-Cryptography-Protocols-Algorithms-Source/dp/0471117099/

I want to cover the equivalent of a typical CS undergrad course in material, so I'm making a list of books to cover the typical topics. I've split the list into topics that, from the research I did, I think are compulsory and optional. I would like some help to confirm if the topics are split correctly, and if the books are of the correct level. Also, please let me know if I left out any important topics, or if any are beyond undergrad level.

Thank you for your time!

Edit regarding the on hold status: I do not believe this question is off-topic as I am not asking for a recommendation for books - I am asking if the topics I have listed are indicative of a typical CS course, and if any important topics are missing. The books links are only there in case the books I have chosen are not correct for the topic, and can be removed if necessary.


COMPULSORY

Operating Systems: Operating System Concepts

Networks: Computer Networking: A Top-Down Approach

Discrete Mathematics: Concrete Mathematics

Data Structures and Algorithms: Introduction to Algorithms

Computer Architecture: Computer Systems: A Programmer's Perspective

Automata Theory: Introduction to the Theory of Computation

Compilers: Engineering a Compiler was recommended to me over the dragon book.

Database Theory: An Introduction to Database Systems

Programming Language Concepts and Design: Programming Language Pragmatics

OPTIONAL

Cryptography: Cryptography Engineering: Design Principles and Practical Applications

Functional Programming: Learn You a Haskell for Great Good!

Artificial Intelligence: Artificial Intelligence: A Modern Approach

Computer Graphics: Real-Time Rendering

Your list is very good on the subjects directly related to computer science. However, it is light on math. In my own B.Sc. in Computer Science I also had a ton of calculus, linear algebra, algebra (groups, rings, etc), statistics, analytic geometry and numerical analysis. Some applications of computer science rely heavily on those:

  • Machine learning depends on lots of linear algebra, calculus, and statistics;
  • Computer graphics depends a lot on analytic geometry and linear algebra;
  • Scientific computation relies on calculus and numerical analysis.

I never used much of the ton of Algebra I had, but I hear it is important for cryptography. :-)

For a programmer developing more regular applications your list is very good, but for those interested in these more specialized areas (which are still pretty important), these subjects are vital.

I want to use CBC MAC in C++. First I hope to find some implementation of block cipher which I will use in CBC mode, which I understand is CBC MAC. But I have two questions:

1) If the length of the message to be authenticated is not multiple of block cipher block length, what shall I do?

2) To strengthen CBC MAC one recommended way as mentioned on Wiki is to put the length of the message in the first block. But how should I encode the length, as string? Or in binary? If block length of cipher is say 64 bits, do I encode the number as 64 bit number? e.g. if message length is 230, I should use following value as first block:

00000000 00000000 00000000 00000000 00000000 00000000 00000000 ‭11100110‬

?

  1. It depends on the 2nd question. You must "pad" the message with something until it is a multiple of the block size. The pad bytes are added to the message before the MAC is calculated but only the original message is transmitted/stored/etc.

    For a MAC, the easiest thing to do is pad with zeros. However this has a vulnerability - if the message part ends in one or more zeros, an attacker could add or remove zeros and not change the MAC. But if you do step 2, this and another attack are both mitigated.

  2. If you prepend the length of the message before the message (e.g. not just in the first block, but the first thing in the first block), it mitigates the ability to sometimes add/remove zeros. It also mitigates an attackers ability to forge a message with an entire arbitrary extra block added. So this is a good thing to do. And it is a good idea for completely practical reasons too - you know how many bytes the message is without relying on any external means.

    It does not matter what the format of the length is - some encoded ASCII version or binary. However as a practical matter it should always be simple binary.

    There is no reason that the number of bits in the length must match the cipher block size. The size of the length field must be large enough to represent the message sizes. For example, if the message size could range from 0 to 1000 bytes long, you could prepend an unsigned 16 bit integer.

    This is done first before the MAC is calculated on both the sender and receiver. In essence the length is verified at the same time as the rest of the message, eliminating the ability for an attacker to forge a longer or shorter message.

There are many open source C implementations of block ciphers like AES that would be easy to find and get working.

Caveat Presumably the purpose of the question is just for learning. Any serious use should consider a stronger MAC such as suggested by other comments and a good crypto library. There are other weaknesses and attacks that can be very subtle so you should never attempt to implement your own crypto. Neither of us are crypto experts and this should be done only for learning.

BTW, I recommend both of the following books by Bruce Schneier:

http://www.amazon.com/Applied-Cryptography-Protocols-Algorithms-Source/dp/0471117099/ref=asap_bc?ie=UTF8

http://www.amazon.com/Cryptography-Engineering-Principles-Practical-Applications/dp/0470474246/ref=asap_bc?ie=UTF8