A short guide to the world of cryptography#

Chap. 1: Basics of Cryptography #

53++!305))6*;4826)4+.)4+);806*;48!8`60))85;]8*:+*8!83(88)5*!;46(;88*96*?;8)*+(;485);5*!2:*+(;4956*2(5*-4)8`8*;4069285);)6!8)4++;1(+9;4808 1;8:8+1;48!85;4)485!528806*81(+9;48;(88;4(+?3 4;48)4+;161;:188;+?;

“But,” said I, returning him the slip, “I am as much in the dark as ever. Were all the jewels of Golconda awaiting me on my solution of this enigma, I am quite sure that I should be unable to earn them.” “And yet,” said Legrand, “the solution is by no means so difficult as you might be led to imagine from the first hasty inspection of the characters. These characters, as any one might readily guess, form a cipher --that is to say, they convey a meaning; but then, from what is known of Kidd, I could not suppose him capable of constructing any of the more abstruse cryptographs. I made up my mind, at once, that this was of a simple species --such, however, as would appear, to the crude intellect of the sailor, absolutely insoluble without the key.”

“And you really solved it?”
(from: Edgar Alan Poe, The Gold-Bug)

Yes, he solved this problem. If Captain Kidd had known more about cryptography, Legrand would not have solved this riddle like that easily.

The following paragraphs will tell you some basics of cryptography. We will show how to protect two different things: messages and connections. A message can be any block of data with a limited length. In practice, this is usually a single file, an email message, a data block in memory, or an object in a database. Stream connections are reliable transport media like TCP net- work connections or pipes. In contrast to messages, these connections can transport data of arbitrary length. In addition, the receiver can already process parts of the data when the sender has not yet sent all data or does not even know the remaining length.

What type of protection can we offer?

Well, with cryptography we can ensure the integrity, the authenticity, and the confidentiality of data. Integrity means that the receiver of data can detect any modification of the data on the way from the sender to the receiver. Authenticity is a property that allows verifying that the data really originates from the alleged sender. With confidentiality we mean a feature that enables the sender to transform the original data in a way that only the designated recipient can reconstruct it. No eavesdropper between sender and receiver can recover the original data. There are different types of cryptographic operations which offer different kinds of protection. We will have a look at the cryptographic operations called hash algorithms, signature schemes, and ciphers.

Hash Functions #

One of the most important cryptographic operations are hash functions. A hash function is an operation which takes data of arbitrary length as input and produces an small output of a fixed size (e.g. 160 bit). This small hash value serves as a representa- tive for the original data. For instance, signatures use this hash value instead of the original data. The hash value is a kind of fingerprint of the complete data.

To be secure, a hash function has to meet certain requirements. Given a hash value, it must be infeasible to compute any input data for which the hash functions produces this value.

It must be practically impossible to create two different input data for which the hash function produces the same hash value.

The hash value can be used to ensure integrity of data. If an application knows the hash value of some original data, it can easily verify the integrity of received data. The application simply calculates the hash value over the received data and compares this value with the original value. If both match, the data is complete and unmodified.

Signature Schemes #

The signature creation function takes data as input and a signature key as parameter. The resulting signature value is of a fixed size (e.g. 1024 bit), similar to a hash value.

The signature verification function takes the data and the signature value as input, and the verification key as parameter. The result is true or false. The verification key is a key corresponding to the signature key which has been used to calculate the given signature value. The result is true if the data is complete and unmodified, and the signature value has been calculated with the signature key corresponding to the used verification key. Otherwise the result is false, and the signature must be rejected. In a secure signature scheme it is impossible to create a valid signature without the signature key. Usually, the signer generates a key pair, keeps the signature key secrete and publishes the verification key along with his name. A relying party checks if the verification key belongs to the alleged signer. If a signature verifies with a verification key which is bound to an entity, this evidences that this entity created the signature. With technical and organizational means it is possible to ensure that only the legitimate owner can use the signature key.

Moreover, using advanced technologies to get authentic verification keys bound to uniquely identifiable entities, cryptographic signatures can serve as an electronic substitute for handwritten signatures. In combination with such techniques, a signature can provide a property called non-repudiation. This means that a verifiable signature can be considered as evidence that a certain person created the signature value, and this person cannot deny this fact.

Ciphers #

To ensure confidentiality we can employ a cipher. There is one function for encryption and another for decryption.

The encryption function takes the confidential data as input and an encryption key as parameter. As output we get the encrypted data. It is safe to send this encrypted data via insecure media like the internet.

For decryption, we have another function. It requires the encrypted data as input and the decryption key as parameter. If the decryption key corresponds to the key used for encryption, we get the original data as result. Provided that used cipher is secure, there is no way to decrypt the data without this decryption key. The decryption key must be kept secret because it is everything required to recover the confidential data.

We can distinguish two types of ciphers. One type uses the same key for encryption and decryption; the sender and receiver must share the secret key. This type is called symmetric cipher. In contrast, asymmetric ciphers use key pairs, consisting of an encryption key and a decryption key. The advantage is that one must only keep the decryption key secret. The encryption key can be published. The drawback is that asymmetric ciphers are about 1000 slower than symmetric ciphers.

Chap. 2: Public Key Infrastructure #

...And when the baker had rubbed his feet over, he ran to the miller and said, “Strew some white meal over my feet for me.” The miller thought to himself, “The wolf wants to deceive someone,” and refused; but the wolf said, “If thou wilt not do it, I will devour thee.” Then the miller was afraid, and made his paws white for him. Truly men are like that. So now the wretch went for the third time to the house-door, knocked at it and said, “Open the door for me, children, your dear little mother has come home, and has brought every one of you something back from the forest with her.” The little kids cried, “First show us thy paws that we may know if thou art our dear little mother.” Then he put his paws in through the window, and when the kids saw that they were white, they believed that all he said was true,...
(From Brothers Grimm, “The Wolf and the Seven Little Kids”)

...but the youngest little goat was still suspicious and cried: “Show us your certificate first, so that we are sure that you are our dear mother!” So the wolf had to go away again, and since he did not know what a certificate was, he asked and learned that he could get one from a certification authority. But no cunning and trickery, and no thread did help him: nobody believed him that he was the goat with the seven little kids and nobody was willing to give him a certificate. Just when he decided to give up he met another wolf who told him about a certification authority that would not ask whether he was a wolf or a goat. The wolf jumped for joy, and when the day was over he had a certificate saying that he was the goat with the seven little kids.

So he went to the goat’s house for the fourth time, knocked and said, “Open the door for me, children, your dear little mother has come home, and has brought every one of you something from the forest with her.” And he put his white dyed paws and his certificate in through the window. The kids discussed about it and then the youngest kid cried: “Sorry, we cannot open the door. You are not our mother. We are not allowed to trust the authority that has issued your certificate!” Hearing this, the wolf got so furious that he ate up his useless certificate.

The certificate, however, stuck in his throat so that he could not breathe anymore and finally dropped dead. Now the seven little kids opened the door, danced around the dead wolf and sang: “The wolf is dead! The wolf is dead!”

A Matter of Trust #

Not trusting the certificate of the wolf has saved the lives of the seven little goats. However, what does this mean for the world of E security? Why is trust so important? For example, when receiving a signed message, shouldn’t it be sufficient to verify its signature? The answer is: No! Verifying the correctness of the signature will only tell us that the message has not been tampered with and that it has been signed with the signer’s private key. It would not tell us who the signer actually is – or, more precisely, if the signer really is who she/he pretends to be. For verifying the signature we only need the signer’s public key; for verifying her/his identity we need her/his certificate.

A certificate binds the public key of some person to her/his name. Certificates are issued by Certification Authorities (CAs) and are usually made publicly available via HTTP download or LDAP databases. Besides name and public key of its owner (subject), a certificate also contains the name of the issuing CA, a unique serial number, and (like a passport) an issuing and expiration date. All these items – and any number of certificate extensions with additional information like, for instance, certificate purpose or email address of the owner – are put together and signed with the private key of the CA.

With this signature the CA confirms that the public key included in the certificate belongs to the entity that is the owner of the certificate. Since the CA is responsible for the information given in a certificate, it should carefully check the identity of the requesting individual. Carefully? Doesn’t the certificate of the wolf say that he is the goat with the seven little kids? Of course, this is only a fairy tale, but in any fairy tale there may be a little bit of truth. And in real life there are CAs that may issue certificates to anybody who comes along. Such certificates, however, may only be used for testing or demonstration purposes. The more critical the purpose of a certificate is, the more carefully a CA’s registration authority has to investigate the identity of the requesting entity. Especially authorities that issue Qualified Certificates for use with advanced electronic signatures in the scope of E commerce and E government must take care for a high assurance level. In any case, before putting trust into a certificate, we should read the policy or practice statement of a CA. If we then do not agree with the CA’s way of working we will not trust the certificates it issues.

Hopefully we have learned our lesson from the seven little kids!

Passports May Be Revoked #

If a certificate is suspected to get misused (e.g. because the corresponding private key has been compromised), it has to be revoked before its validity period has expired. Revocation means that the CA puts the certificate’s serial number on a publicly available revocation list (CRL). If we are verifying a certificate, we don’t have to forget to look at the CRL to ensure that the certificate is still valid. Since CRLs may grow with their entries, more and more CAs provide revocation information via the more efficient client-server based Online Certificate Status Protocol (OCSP).

We Build a Certification Tree #

Of course, not only human beings may get a certificate; a CA also may certify organizations, web-servers, etc. and other (sub) CAs. Each sub CA itself again may certify any number of further CAs and so a tree-like certification structure may pop up having final end user certificates at it leaves and one single top level CA certificate at its root.

Since nobody can reside above the root of the tree, the top level CA holds a selfsigned certificate; i.e. it certifies its public key with its own private key. Building and validating a path that leads from some leaf of the tree to the root is often a very tricky action. However, usually we do not have to walk the whole way; we can stop as soon as we have found a CA in the path we explicitly want to trust. Such a CA is called a trust anchor.

Again: it’s a Matter of Trust #

All together, certificates, revocation lists, certification authorities, certified entities, etc. are what we call a Public Key Infrastructure (PKI). Unlike the famous web of trust of the popular PGP protocol, the X.509 PKI system of the PKIX working group at IETF has propagated a more hierarchical trust model that is based on certification authorities, as described above. This makes X.509 more suitable for the large Internet community: if we place trust in one particular CA, we also trust any CA that is located beyond this trust anchor in the tree; down to the end users at the final leaves. The seven little kids did not trust the CA that has issued the certificate of the wolf, and consequently they did not trust the wolf himself. So finally we have returned to the point where we have started our journey: it is all a matter of trust!

Chap. 3: Key Management #

...Ali Baba saw the robbers, as soon as they came under the tree, each unbridle his horse and hobble it. Then all took off their saddlebags, which proved to be full of gold and silver. The man who seemed to be the captain presently pushed forward, load on shoulder, through thorns and thickets, till he came up to a certain spot, where he uttered these strange words: “Open, Sesame!” And forthwith appeared a wide doorway in the face of the rock. The robbers went in, and last of all their chief, and then the portal shut of itself.

Long while they stayed within the cave whilst Ali Baba was constrained to abide perched upon the tree, reflecting that if he came down, peradventure the band might issue forth that very moment and seize him and slay him. At last he had determined to mount one of the horses and driving on his asses, to return townward, when suddenly the portal flew open. The robber chief was first to issue forth, then, standing at the entrance, he saw and counted his men as they came out, and lastly he spoke the magical words, “Shut, Sesame!” whereat the door closed of itself. When all had passed muster and review, each slung on his saddlebags and bridled his own horse, and as soon as ready they rode off, led by the leader, in the direction whence they came. Ali Baba remained still perched on the tree and watched their departure, nor would he descend until what time they were clean gone out of sight, lest perchance one of them return and look around and descry him.

Then he thought within himself: “I too will try the virtue of those magical words and see if at my bidding the door will open and close.” So he called out aloud, “Open, Sesame!” And no sooner had he spoken than straightway the portal flew open and he entered within...
(From: “Ali Baba and the forty thieves” of 1001 Nights)

The words “Open, Sesame!” were the key to the cave of the thieves. By using it carelessly, the thieves enabled Ali Baba to hear these words easily.

For all cryptographic operations which use keys, it is essential to handle the keys appropriately. For instance, if an application uses a cipher to protect data, it must protect the decryption key. A system cannot be safer than its weakest part. An insufficiently protected sensitive key can compromise the complete system. In the case of digital signatures, key protection can be especially critical. If signatures are expected to offer non repudiation, a signer cannot deny having created a signature if it verifies with a certain verification key. Therefore, an attacker who is able to steal a signature key can create valid signatures in the name of the key owner, and the owner may be liable for these forged signatures. An adequate key protection is indispensable.

There are several methods commonly used in practice. They offer a different degree of protection; this means, some of them can withstand attacks with a higher attack potential than others. The level of protection needed depends on the value of the assets to be protected. Private emails with no information of public interest may be a less attractive target than sensitive information of a government.

The simplest method to keep a key is to store it in plain on a disk or some other persistent memory. This method is only as safe as the disk. If someone gains access to the disk, it is easy to make a copy of the key. In practice, keys are rarely stored in plain. Usually, they are protected with a password or PIN. This requires having access to the storage media and knowing the password.

For higher security, there are more advanced technologies. Dedicated hardware like smart cards can protect against heavy attacks. Even security experts with a big budget are unable to extract sensitive keys from a modern smart card. The essence of cryptographic smart cards is that they are constructed in a manner that the keys can never leave the card. The cards have a processor and software, which generate the keys, use the keys and destroy the keys. The cards do not have any interface to extract the keys—for nobody. Thus, the cards work differently than a simple disk. They are not just a key storage, they are rather computers themselves. It is no longer the host system which does the actual cryptographic operation like signature creation.

The host sends the data to be signed to the smart card, the smart card does the signature creation and then returns the result to the host computer.

So called hardware security modules (HSMs) are similar to smart cards and offer a comparable level of protection, but they have more memory for keys and the have a much higher performance. HSMs are available in different forms: PCI cards, SCSI devices or network devices. The main application for HSMs are server applications which need a high level of security; examples are applications which sign public documents or issue certificates. Dedicated crypto hardware also can improve the performance of a server application significantly, because it can process cryptographic operations much faster than the multi-purpose CPUs of most host systems.

There are multiple interface standards through which an application can access smart cards or HSMs. The most frequently used are PKCS#11 and Microsoft Crypto API. The Microsoft Crypto API is an integral part of all current versions of Microsoft Windows, and most Microsoft applications use this interface for cryptographic operations. This includes email clients, web browser as well as web servers. A main drawback is that it is only available on Windows platforms. The PKCS#11 API is available on almost all platforms including Windows, Linux, Solaris and Unix systems. Smart card vendors usually support both interfaces, HSM vendors typically support at least PKCS#11.

Chap. 4: Secure Connections – SSL and TLS #

“I am overhearing them.”
“Pshaw! Sneaking and overhearing seems to be your favorite pleasure! But keep in mind, that now you are neither at the boondocks nor in the dark and bloody grounds!”
“What does it matter? Shouldn’t it be possible to eavesdrop here, too?”
“Well; but you find out nothing from it.”
“You find out all what you want to know!”
(From Karl May, “An der Tigerbrücke” (In: “Am stillen Ozean”))

But just in case the conversation is not protected by SSL!

Sure, Old Shatterhand is a well languaged guy and a real champion when sneaking and overhearing hostile Indians. But none of his abilities would help him when trying to crack the AES or TripleDES algorithm in order to find out where the Internet Tramps will complete their next coup. Poor Charlie, you would be lost in the era of E-security!

However, if data is exchanged via the Internet without any cryptographic protection, today it would be much easier to steal the required information. Cautious and dangerous sneaking actions wouldn’t be necessary anymore! For this reason you should be aware of the risks you may take when exchanging critical data over the Internet. And it would probably not be a well-behaved fellow man like Winnetou or Old Shatterhand who is overhearing you for taking advantage of unauthorizedly accessed information.

Do Not Send Your Data Via Plain HTTP! #

Just imagine a situation where you are ready to finish your order in an online store by entering your credit card number. Before pressing the ok button to send your confidential data to the store – and possibly to any eavesdropper that is sniffing on the line – you should make sure that the data will not travel over plain HTTP only. Neither TCP nor http provides any kind of protection mechanisms against passive (where the “man in the middle” can read your data) or active (where he is going to modify it) attacks. This might be ok if you are surfing the Web for fun during your spare time, but is not acceptable for critical applications like online shopping, telebanking or E-government.

HTTPS: The “S” Makes It Secure! #

SSL turns HTTP into HTTPS, and from now on we are on the secure side! SSL stands for Secure Sockets Layer. It is an application-independent client- server security protocol that operates over a reliable transport protocol (typically TCP). With the help of SSL, any higher level application protocol like HTTP, FTP or TELNET, can be protected by means of the following security services:

• Server- (and maybe client-) authentication using public key cryptography
• Confidentiality of the data by using symmetric cryptography
• Integrity of the data by using message authentication codes

The SSL protocol has been developed by Netscape. The original version (SSL 2.0) had some serious limitations and security problems, and it has therefore been replaced by its thoroughly re-designed successor version SSL3.0. TLS 1.0 (Transport Layer Security) has been standardized by the Internet Engineering Task Force (IETF). It is nearly identical to SSL3.0, containing some minor updates. In the course of time, several attacks have been published against the SSL/TLS protocol, some of them less, some of them more serious ones, but none of them launched by Old Shatterhand! Effective countermeasures against all these attacks have been developed and implemented.

It Starts With a Handshake and Ends With a Secure Channel #

TLS security is channel-based. First client and server go into an initial handshake phase to agree upon a so called cipher suite, defining the cryptographic parameters for the following session. As soon as the handshake is finished, a secure channel is set up. From now on any data that travels over the channel is protected by applying the cryptographic mechanisms negotiated during the handshake. The general handshake proceeding may look like the following conversation: The client starts the handshake and invites the server to install a secure connection: The client starts the handshake and invites the server to install a secure connection: “Hello, Mr. Server. How are you? My boss has told me to set up a secure conversation. Here are my favorite cipher suites: First I would kindly ask you to authenticate yourself with an RSA certificate. I am sorry, but this is the only type of certificate I am able to read! However, I am more flexible with respect to the symmetric cipher algorithm. Although I would prefer to use AES for encrypting the data, it would also be ok to take RC4 or TripleDES. The MAC calculation should be done by means of the SHA 1 algorithm! Please tell me if any of these options would be suitable for you!”

Since Mr. Server is able to support all the favorite algorithms of the client, he sends his approval: “Have a nice day, Mr. Client! RSA, AES and SHA 1 are ok for me. Here comes my certificate. I am very sorry, but I have to ask you to authenticate yourself, too. Please send me your certificate!”

The client, after verifying the server’s certificate, now in response has to send his own certificate to fulfill the client authentication request. If he does not do this (maybe he is not able to) it is up to the server to say “Sorry, but I cannot let you in without your certificate! Farewell and Goodbye”, or he can accept the anonymity of the client.

After creating and (securely) exchanging a secret session key, client and sever start the secure data exchange: “Now we say goodbye to all the spies on the line. Let the encrypted data flow!”

And Mr. Shatterhand? He would probably say something like: “Hell and damnation! What’s that? I hear the voice, but I can’t understand anything!”

Chap. 5: Secure Messaging #

After a year the King had to take the field, so he commended his young Queen to the care of his mother and said, “If she is brought to bed take care of her, n u r s e her well, and tell me of it at once in a letter.” Then she gave birth to a fine boy. So the old mother made haste to write and announce the joyful news to him. But the messenger rested by a brook on the way, and as he was fatigued by the great distance, he fell asleep. Then came the Devil, who was always seeking to injure the good Queen, and exchanged the letter for another, in which was written that the Queen had brought a monster into the world. When the King read the letter he was shocked and much troubled, but he wrote in answer that they were to take great care of the Queen and nurse her well until his arrival. The messenger went back with the letter, but rested at the same place and again fell asleep. Then came the Devil once more, and put a different letter in his pocket, in which it was written that they were to put the Queen and her child to death. The old mother was terribly shocked when she received the letter, and could not believe it. She wrote back again to the King, but received no other answer, because each time the Devil substituted a false letter, and in the last letter it was also written that she was to preserve the Queen’s tongue and eyes as a token that she had obeyed.
(From: Brothers Grimm, “The Girl without Hands”)

Diabolic competition for Bruce Schneier’s famous crypto villains Eve and Mallory? Nobody else than Lucifer himself has left the hell house to come on earth and tamper the correspondence of honest mortals! He does not only ignore the privacy of letters and reads a message which was not addressed to him, he also makes an active attack and forges the contents of any letter he can catch up. We do not really believe that the story would take a better course if we would transfer it to the present day where king and mother would have the chance to benefit from the achievement of electronic mail. We are afraid that they again would be innocent enough to send their messages in clear over the internet. An attacker wouldn’t even have to unseal a nonexistent cover for reading the contents of a message and forge it as he like. Sure, we cannot be aware about the cryptographic genius of the Devil; nevertheless we want to show you how you can protect your electronic documents and messages against attacks that are not supernatural.

From SMTP to MIME; from MIME to S/MIME #

Internet mail is based on the Simple Mail Transfer Protocol (SMTP). SMTP, however, restricts messages to contain only 7 bit US-ASCII characters. This may be suitable for pure text messages, but not for multimedia data like pictures, audio or video material. MIME (Multipurpose Internet Mail Extensions) extends SMTP about the ability to handle arbitrary binary data. Both, STMP and MIME do not contain any security mechanisms for protecting a message when traveling through the wide and open internet. This drawback has finally led to the introduction of the S/MIME (Secure MIME) protocol. Today any notable email client, like Microsoft Outlook or Mozilla Messenger, is able to speak S/ MIME

S/MIME relies on CMS #

S/MIMEv2 gets its cryptographic capabilities from the PKCS#7 protocol, which specifies several cryptographic mechanisms for digitally signing, digesting, encrypting or authenticating any kind of data. The successor versions of PKCS#7 and S/MIMEv2, CMS (Cryptographic Message Standard) and S/MIMEv3, respectively, take both care of algorithm independence and they introduce additional content formats and processing rules. Furthermore, S/MIMEv3 has been enhanced by new security features especially designed for business and finance applications.

Digital Signature and Digital Envelope #

Based on the cryptographic functionalities of CMS, S/MIME provides the following security services:

• Authenticity, Integrity and Non-repudiation by means of digital signatures
• Privacy and Confidentiality by means of digital envelopes

When signing a document with your private key you make sure that it cannot be forged. At the same time you agree on being responsible for the content of the document. For providing proof of your identity, you add your certificate to the document.

A digital envelope is a hybrid technique. It uses a combination of asymmetric and symmetric cryptography to encrypt a document for some indented recipient only. Since asymmetric cryptography is comparably slow, you first create a symmetric (temporary) content encryption key and use it to encrypt the content data. Then you encrypt the content encryption key with the recipient’s public key retrieved from her/his certificate – and send both, encrypted content and encrypted secret key to the recipient. Now the recipient uses her/his private key to decrypt the content encryption key which finally enables him to decrypt the encrypted content.

As you can see above, any cryptographic information like certificate or content encryption key that may be required by the recipient for verification or decryption, respectively, is packed with the message itself. This is an essential difference to connection- based protocols like TLS, where all the data is exchanged over a secure channel.

XMLDSIG and XML Encryption #

Unlike CMS, which encloses signature and encryption formats into one single specification, the XML world defines two separate standards: XMLDSIG and XML ENCRYPTION.

The “XML Signature Syntax and Processing” standard (XMLDSIG) describes the format of a signed message in XML. It specifies the processing necessary to sign and verify such a signed message, respectively. Example applications are security features of markup languages such as Security Assertion Markup Language (SAML), or XMLbased protocols like Simple Object Access Protocol (SOAP). The Austrian government makes heavy use of XMLDSIG for its E-Government services (“Austrian Citizen Card”).

The W3C standard “XML Encryption Syntax and Processing” specifies the way how to encrypt, respectively decrypt, XML data as well as arbitrary data and represent the encryption information as XML. It is closely related to the XMLDSIG standard.

Conclusion #

And the morale of the whole story? If king and mother would have signed their letters, the Devil would have not been able to forge their messages; if they additionally would have encrypted them, he would not have been able to read their contents...