Cryptography, Encryption, Hash Functions and Digital Signature

Eray ALTILI
Feb 17, 2018 · 15 min read

Cryptography is at the heart of Blockchain technology. At this post, I will try to explain some of the basics of Cryptography, Encoding,Encryption and Digital Signature.

Encoding is the process of applying a specific code, such as letters, symbols and numbers, to data for conversation into an equivalent cipher.

The difference between encoding and encryption is that encryption needs a key to encrypt/decrypt.

Cryptography

Cryptography is the practice and study of secure communication in the presence of third parties.[1] In the past cryptography referred mostly to encryption. Encryption is the process of converting plain text information to cipher text. Reverse is the decryption. Encryption is a mechanism to make the information confidential to anyone except the wanted recipients. Cipher is the pair of algorithm that creates encryption and decryption. Cipher operation is depends on algorithm and the key. Key is the secret that known by communicants. In addition, there are two types of encryption by keys used:

Symmetric Key Algorithms
Symmetric key algorithms (Private-key cryptography): same key used for encryption and decryption. (AES, DES etc.) (AWS KMS uses Symmetric Key Encryption to perform encryption and decryption of the digital data)

Symmetric key ciphers implemented as either block ciphers or stream ciphers by type of input data. A block cipher enciphers input in blocks of plaintext as opposed to individual characters, the input form used by a stream cipher.

Block Ciphers: encrypt block of data of fixed size. (DES, AES etc.)
Stream Ciphers: encrypt continuous streams of data. (RC4, etc.)

Entropy measures how random data is when used in cryptography.

Asymmetric Key Algorithms
Asymmetric key algorithms (Public-key cryptography): two different keys (private and public) used for encryption and decryption. (RSA, Elliptic Curve etc.)(AWS EC2 key pairs uses asymmetric encryption.)

Data manipulation in symmetric systems is faster than asymmetric systems as they generally use shorter key lengths. Asymmetric systems use a public key to encrypt a message and a private key to decrypt it. Use of asymmetric systems enhances the security of communication however; it consumes CPU resources heavily.

Cryptographic Hash Functions

Cryptographic hash functions are a third type of cryptographic algorithm. A message of any length taken as input, and output to a short, fixed length hash. (MD5, SHA etc.) It is a mathematical algorithm that maps data of arbitrary size to a bit string of a fixed size (a hash) and designed to be a one-way function, that is infeasible to invert. Integrity checking is the mechanism to verify if the information has not changed. To validate the integrity, a thumbprint (also called hash or digest) of the information created. Thumbprint created by an algorithm that create a shorter bit string from an information.

SALT

Random string, or salt, is added to the password (to make the password more secure) and then hashed. This prevents rainbow table attacks. Salting should be used with Cryptographically Secure Pseudo Random Number Generator aka CSPRNG. Salts needs to have high entropy. However RSA used Dual_EC_DRBG standard for CSPRNG which has been shown not be cryptographically secure and is believed to have a kleptographic NSA backdoor. Backdoor was confirmed in 2013 and RSA Security received a $10 million payment from the NSA to do so.

Key Stretching

A cryptographic hash function or a block cipher may be repeatedly applied in a loop. Modern password-based key derivation functions, such as PBKDF2, use a cryptographic hash, such as SHA-2, a longer salt (e.g. 64 bits) and a high iteration count (tens or hundreds of thousands).


Authenticated Encryption

Authenticated encryption provides confidentiality, data integrity, and authenticity assurances on encrypted data. Authenticated encryption can be generically constructed by combining an encryption scheme and a message authentication code (MAC). For example AWS KMS Encrypt API takes plaintext, a customer master key (CMK) identifier, and an encryption context ( Encryption context is a set of non-secret key-value pairs that you can pass to AWS KMS when you call the Encrypt, Decrypt, ReEncrypt, GenerateDataKey, or GenerateDataKeyWithoutPlaintext APIs.) and returns ciphertext. The encryption context represents additional authenticated data (AAD). The encryption process uses the AAD only to generate an authentication tag. The tag is included with the output ciphertext and used as input to the decryption process. This means that the encryption context that you supply to the Decrypt API must be the same as the encryption context you supply to the Encrypt API. Otherwise, the encryption and decryption tags will not match, and the decryption process will fail to produce plaintext. Further, if any one of the parameters has been tampered with — specifically if the ciphertext has been altered — the authentication tag will not compute to the same value that it did during encryption. The decryption process will fail and the ciphertext will not be decrypted.

Digital Signature

Digital signature is a mathematical scheme for demonstrating the authenticity of digital messages or documents. A valid digital signature enables information integrity (using hash algorithm) to ensure message is not altered, message created by the sender (authentication) and sender cannot deny having sent the message (non-repudiation). The digital signature has to be authentic, unfalsifiable, non-reusable, unalterable and irrevocable. When all this property are gathered, the authenticity and the integrity of an information can verified.

The signature operation is based on asymmetric cryptography. First a digest of the initial information is created and this last is encrypted with the private key. This operation is called the signature.

To validate the signature, the recipient extracts the encrypted digest from the message and use his public key to unencrypt it. Next the recipient creates a digest from the received information and compare it with the previously unencrypted digest. This is the signature checking process.

A good way to remember when the private key is used is to know what information is important in each operation. In signature process, the critical information is the digest so the private key is used to sign. In encryption process, the critical information is encrypted: so the private key is used to unencrypt.

Modern Encryption[2]

Each encryption algorithm has advantages and convenient therefore Modern Encryption associates both symmetric and asymmetric techniques. Modern algorithm uses a session key (temporarily key) to encrypt information with symmetric cryptography. Next, the session key encrypted with the public key of the recipient. To unencrypt information, first the recipient unencrypt the session key with his private key and unencrypt information with the session key [2].

On the sender side, following actions performed:

1. A temporarily key called session key (Ks) generated;

2. Information encrypted with session key (Ks);

3. (Ks) Encrypted with the public key (Kpu) of the recipient. This key called Kse;

4. Kse added to the encrypted information file. This file sent to the recipient.

On the recipient side, the below action performed:

  1. The encrypted information and Kse are separated;
  2. The Kse key is unencrypt with the private key (Kpr) of the recipient and becomes the Ks;
  3. The document is unencrypted with Ks.

Encryption and Digital Signature Operation

Now that we are aware about encryption, hash algorithm and signature, let have a look how these elements interact together to make an information confidential, authentic and honest.

When the signature and encryption used together, the signing process done first. Following steps performed:

1. A digest is created from the initial information;

2. This thumbprint is encrypted with the private key (Kprg);

3. The thumbprint is added to the initial information (in the same file);

4. A temporarily session key is generated (Ks) It will be used to encrypt initial information;

5. The session key is encrypted (Kse) with the public key of the rececipient (Kpub);

6. Kse added to encrypted information file. So this file is contains the encrypted information, the Kse and the signature.

When the recipient receives the file from the issuer, it begins by unencrypt file and next to verify the signature:

1. The recipient extract the Kse from the received file. This key is unencrypt with the private key (Kprb) to obtain session key (Ks);

2. Ks is used to unencrypt information;

3. Next recipient extract the encrypted thumbprint;

4. The public key (Kpug) is used to unencrypt the thumbprint;

5. In the same time, the recipient creates a digest from the previously unencrypted information;

6. To finish, the recipient compares the unencrypted thumbprint with the digest generated from unencrypted information. If they match, the signature verified.

Proxy Reencryption

A proxy re-encryption is generally used when one party, say Bob, wants to reveal the contents of messages sent to him and encrypted with his public key to a third party, Chris, without revealing his private key to Chris. Bob does not want the proxy to be able to read the contents of his messages. Bob could designate a proxy to re-encrypt one of his messages that is to be sent to Chris. This generates a new key that Chris can use to decrypt the message. Now if Bob sends Chris a message that was encrypted under Bob’s key, the proxy will alter the message, allowing Chris to decrypt it. This method allows for a number of applications such as e-mail forwarding, law-enforcement monitoring, and content distribution.

An unidirectional multi-use proxy re-encryption (UM-PRE) scheme allows a semi-trusted proxy to transform a message encrypted under the key of party A into another ciphertext, containing the initial plaintext, such that another party B can decrypt the ciphertext with its key. The proxy neither gets access to the plaintext nor to the decryption keys. The proxy can only transform in one direction and one ciphertext can be transformed multiple times.

Proxy re-encryption is a form of public-key encryption that allows a user Alice to “delegate” her decryption rights to another user Bob.

In a proxy re-encryption scheme, Alice delegates a semi-trusted proxy to translate cyphertexts encrypted under her key into cyphertexts encrypted under Bob’s key. Once delegated, the proxy operates independently of Alice. The proxy is considered “semi-trusted” because it does not see the content of the messages being translated, nor can it re-encrypt Alice’s messages to users for whom Alice has not granted decryption rights.

To delegate her decryption rights to Bob, Alice generates a “delegation key” (or “re-encryption key”), and sends this key to the proxy server. The proxy server uses this key to translate messages from Alice’s key to Bob’s key. The schemes implemented by Proxy server are unidirectional. In a unidirectional scheme, delegations are “one-way”, i.e., the proxy can re-encrypt Alice’s messages to Bob, but cannot re-encrypt Bob’s messages to anyone. Furthermore, Alice can generate a delegation key (to Bob) using only Bob’s public key (and her secret key). It is not necessary that Bob be online or even know that delegation has taken place.

Proxy Reencryption Functions

Proxy re-encryption schemes are similar to traditional symmetric or asymmetric encryption schemes, with the addition of two functions:

Delegation — allows a message recipient (keyholder) to generate a re-encryption key based on his secret key and the key of the delegated user. This re-encryption key is used by the proxy as input to the re-encryption function, which is executed by the proxy to translate ciphertexts to the delegated user’s key. Asymmetric proxy re-encryption schemes come in bi-directional and uni-directional varieties.

In a bi-directional scheme, the re-encryption scheme is reversible — that is, the re-encryption key can be used to translate messages from Bob to Charlie, as well as from Charlie to Bob. This can have various security consequences, depending on the application. One notable characteristic of bi-directional schemes is that both the delegator and delegated party (e.g., Charlie and Bob) must combine their secret keys to produce the re-encryption key.

A uni-directional scheme is effectively one-way; messages can be re-encrypted from Bob to Charlie, but not the reverse. Uni-directional schemes can be constructed such that the delegated party need not reveal its secret key. For example, Bob could delegate to Charlie by combining his secret key with Charlie’s public key.

Transitivity — Transitive proxy re-encryption schemes allow for a ciphertext to be re-encrypted an unlimited number of times. For example, a ciphertext might be re-encrypted from Bob to Charlie, and then again from Charlie to David and so on. Non-transitive schemes allow for only one (or a limited number) of re-encryptions on a given ciphertext. Currently, the only known uni-directional, transitive proxy re-encryption is done through the use of Homomorphic Encryption which allows computation on encrypted data.

Identity-based conditional proxy re-encryption (IBCPRE)

Proxy re-encryption (PRE) is a useful cryptographic primitive in which a semi-trusted proxy agent is given delegation power to transform a ciphertext for Alice into a ciphertext for Bob without viewing the underlying plaintext. Attribute Based Encryption (ABE) is a promising cryptographic algorithm that provides confidentiality of data along with owner-enforced fine-grained access control. With attribute-based encryption, a data owner can use a set of attribute values (i.e., access policy) for encrypting a message such that only authorized entity who possesses the required set of attribute values can decrypt the ciphertext. A proxy re-encryption scheme using the merits of ciphertext-policy anonymous attribute-based encryption. The scheme, termed as PRE-AABE, reduces the computation burden significantly for updating the access policy of a ciphertext to a semi-trusted proxy agent (e.g., cloud server). The PRE-AABE scheme hides the access policy inside the ciphertext, so that parties except the intended receiver will not be able to figure out the purpose of the ciphertext. At the same time, the proxy agent is able to perform the re-encryption successfully without learning anything about the plaintext contents or the access policy.

An IBCPRE scheme is a natural extension of proxy re-encryption on two aspects. The first aspect is to extend the proxy re-encryption notion to the identity-based public key cryptographic setting. The second aspect is to extend the feature set of proxy re-encryption to support conditional proxy re-encryption. By conditional proxy re-encryption, a proxy can use an IBCPRE scheme to re-encrypt a ciphertext but the ciphertext would only be well-formed for decryption if a condition applied onto the ciphertext together with the re-encryption key is satisfied. This allows fine-grained proxy re-encryption and can be useful for applications such as secure sharing over encrypted cloud data storage.

Under the identity-based cryptographic setting, the public key of the user can be an arbitrary string of bits provided that the string can uniquely identify the user in the system. The unique string, for example, can be an email address, a phone number, and a staff ID (if used only internally within an organization). However, the corresponding private key is no longer generated by the user. From the public key, which is a unique binary string, there is a key generation center (KGC), which generates and issues the private key to the user. The KGC has a public key, which is assumed to be publicly known, and the encryption and decryption then work under the unique binary string defined public key and the corresponding private key, respectively, with respect to the KGC’s public key.

Proxy Re-encryption allows a ciphertext, which originally can only be decrypted by a user, to be transformed by a public entity, called proxy, to another ciphertext so that another user can also decrypt. Suppose the two users are Alice and Bob. Alice has some messages: M1, M2, … Mn. She intends to encrypt them under her public key, and then upload the encrypted messages to some server.

Now when Alice wants to share these n encrypted messages with Bob, Alice can use a proxy re-encryption scheme to allow the server to re-encrypt these n encrypted messages so that Bob can decrypt these re-encrypted messages directly using his own private key.

To do so in the proxy re-encryption scheme, Alice uses her private key and the public key of Bob to generate a re-encryption key. Alice then sends the re-encryption key to the server. Upon receiving this re-encryption key, the server uses the key to transform all the n encrypted messages C1, C2, …, Cn to a new form denoted as D1, D2, …, Dn. Bob can then download D1, D2, …, Dn, decrypt them, and recover the messages M1, M2, … Mn using his private key.

In an identity-based conditional proxy re-encryption (IBCPRE) system, users set their public keys as unique identities of the users. One of the main advantages of using identity-based cryptographic algorithms is the elimination of public key certificates which can help enhance the usability of the target security applications. The term ‘Conditional’ in IBCPRE refers to an additional feature, which allows each encrypted message to have a ‘tag’ associated with. In addition to the tag, each re-encryption key also has a ‘tag’ attached. The IBCPRE is designed so that only if the tag of an encrypted message matches with the tag of a re-encryption key can the encrypted message be re-encrypted.

One of the key features of IBCPRE is that when Alice as a data owner encrypts messages, the encryption is done for herself and only Alice herself can decrypt the encrypted messages using her secret key. There is no need for Alice to know in advance about who that she would like to share the encrypted messages with. In other words, picking the friends to share with by Alice can be done after she encrypts the messages and uploads to the Server.

Another feature of IBCPRE is that it supports end-to-end encryption. The server which stores the encrypted messages cannot decrypt the messages both before and after the re-encryption.

IBCPRE supports one-to-many encryption. The data owner Alice can choose multiple friends to share her data with. For multiple friends to share the encrypted messages with, Alice simply needs to generate a re-encryption key for each of her friends and sends all the re-encryption keys to the server for carrying out the re-encryption. The number of re-encryption keys that Alice needs to generate depends on the number of friends that Alice wants to share the encrypted messages with. It does not depend on the number of encrypted messages. One re-encryption key will allow the Server to convert all the encrypted messages provided the tag of the encrypted messages and the tag of the re-encryption key matches.

The conditional ‘tag’ of the IBCPRE facilitates the fine-grained access of encrypted messages. By setting different tag values onto different encrypted messages, the data owner Alice can control the exact set of encrypted messages that she wants to share with any particular friends of her with great flexibility.

Consider a user Alice who encrypts some messages M1, M2, …, Mt with a tag ‘Private’, Mt+1, Mt+2, …, Mm with a tag ‘toShareWithFamily’, Mm+1, Mm+2, …, Mn with a tag ‘toShareWithFriend’, using IBCPRE under her unique identity, which is considered as the public key of Alice. Alice then uploads the corresponding encrypted messages C1, C2, …, Ct, Ct+1, …, Cm, Cm+1, …, Cn to a server.

When Alice is about to share Mm+1, Mm+2, …, Mn with another user Bob, who becomes her friend recently, Alice generates a re-encryption key using IBCPRE with an associated tag ‘toShareWithFriend’. This generation is done by taking as input Alice’s private key and Bob’s identity. Then Alice sends the re-encryption key to the server. By using the re-encryption key, the server runs the IBCPRE re-encryption function on Cm+1, Cm+2, …, Cn for transforming them into another form, Dm+1, Dm+2, …, Dn so that Bob can decrypt them directly using his private key. This transformation can be done as the tag associated with the encrypted messages, namely ‘toShareWithFriend’, matches with the tag associated with the re-encryption key.

Note that the server cannot transform C1, C2, …, Ct, Ct+1, …, Cm to another form for Bob to decrypt using the re-encryption key because the tag of these m encrypted messages, namely ‘Private’ or ‘toShareWithFamily’, does not match with the tag of the re-encryption key.

Originally published at https://www.linkedin.com on February 17, 2018.

References:

[1] “Cryptography”. In J. Van Leeuwen. Handbook of Theoretical Computer Science

[2] Romain Serre Introduction to Encryption and Signature

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade