NIST hash function competition SHA-3

NIST SHA3

The NIST hash function competition is an open competition held by the US National Institute of Standards and Technology for a new SHA-3 function to replace the older SHA-1 and SHA-2, which was formally announced in the Federal Register on November 2, 2007. "NIST is initiating an effort to develop one or more additional hash algorithms through a public competition, similar to the development process for the Advanced Encryption Standard (AES)."

Submissions were due October 31, 2008, with a list of candidates accepted for the first round published December 9, 2008. NIST held a conference in late February 2009 where submitters gave presentations on their algorithms and NIST officials discussed criteria for narrowing down the field of candidates for Round 2. The list of 14 candidates accepted to Round 2 was published on July 24, 2009. Another conference was held August 23-24, 2010 (after CRYPTO 2010) at the University of California, Santa Barbara, where the second-round candidates were discussed. The announcement of the final round candidates occurred on December 10, 2010 and the proclamation of a winner and publication of the new standard are scheduled to take place in 2012.

Finalists

NIST has selected five SHA-3 candidate algorithms to advance to the third (and final) round:
BLAK
Grøstl (Knudsen et al.)
JH
Keccak (Keccak team, Daemen et al.)
Skein (Schneier et al.)


NIST noted some factors that figured into its selection as it announced the finalists:

Performance: "A couple of algorithms were wounded or eliminated by very large [hardware gate] area requirement – it seemed that the area they required precluded their use in too much of the potential application space."

Security: "We preferred to be conservative about security, and in some cases did not select algorithms with exceptional performance, largely because something about them made us 'nervous,' even though we knew of no clear attack against the full algorithm."

Analysis: "NIST eliminated several algorithms because of the extent of their second-round tweaks or because of a relative lack of reported cryptanalysis – either tended to create the suspicion that the design might not yet be fully tested and mature."

Diversity: The finalists included hashes based on different modes of operation, including the HAIFA and sponge hash constructions, and with different internal structures, including ones based on AES, bitslicing, and alternating XOR with addition.

NIST has released a report explaining its evaluation algorithm-by-algorithm.

Meltem Sönmez Turan's Blog

Deniable Encryption

In cryptography and steganography, deniable encryption is encryption that allows its users to convincingly deny the fact that the data is encrypted or, assuming that the data is obviously encrypted, its users can convincingly deny that they are able to decrypt it. Such convincing denials may or may not be genuine, e.g., although suspicions might exist that the data is encrypted, it may be impossible to prove it without the cooperation of the users. In any case, even if the data is encrypted then the users genuinely may not have the ability to decrypt it. Deniable encryption serves to undermine an attacker's confidence either that data is encrypted, or that the person in possession of it can decrypt it and provide the associated plaintext.

Normally ciphertexts decrypt to a single plaintext and hence once decrypted, the encryption user cannot claim that he encrypted a different message. Deniable encryption allows its users to decrypt the ciphertext to produce a different (innocuous but plausible) plaintext and insist that it is what they encrypted. The holder of the ciphertext will not have the means to differentiate between the true plaintext, and the bogus-claim plaintext.

Deniable encryption allows an encrypted message to be decrypted to different sensible plaintexts, depending on the key used, or otherwise makes it impossible to prove the existence of the real message without the proper encryption key. This allows the sender to have plausible deniability if compelled to give up his or her encryption key. The notion of "deniable encryption" was introduced by Julian Assange & Ralf Weinmann in the Rubberhose filesystem and explored in detail in a paper by Ran Canetti, Cynthia Dwork, Moni Naor, and Rafail Ostrovsky in 1996.

Modern forms of deniable encryption

Modern deniable encryption techniques exploit the pseudorandom permutation properties of existing block ciphers, making it cryptographically infeasible to prove that the ciphertext is not random padding data generated by a cryptographically secure pseudorandom number generator. This is used in combination with some decoy data that the user would plausibly want to keep confidential that will be revealed to the attacker, claiming that this is all there is. This form of deniable encryption is sometimes referred to as "steganographic encryption".

One example of deniable encryption is a cryptographic filesystem that employs a concept of abstract "layers", where each layer would be decrypted with a different encryption key. Additionally, special "chaff layers" are filled with random data in order to have plausible deniability of the existence of real layers and their encryption keys. The user will store decoy files on one or more layers while denying the existence of others, claiming that the rest of space is taken up by chaff layers. Physically, these types of filesystems are typically stored in a single directory consisting of equal-length files with filenames that are either randomized (in case they belong to chaff layers), or cryptographic hashes of strings identifying the blocks. The timestamps of these files are always randomized. Examples of this approach include Rubberhose filesystem and PhoneBookFS.

Another approach utilized by some conventional disk encryption software suites is creating a second encrypted volume within a container volume. The container volume is first formatted by filling it with encrypted random data and then initializing a filesystem on it. The user then fills some of the filesystem with legitimate, but plausible-looking decoy files that the user would seem to have an incentive to hide. Next, a new encrypted volume (the hidden volume) is allocated within the free space of the container filesystem which will be used for data the user actually wants to hide. Since an adversary cannot differentiate between encrypted data and the random data used to initialize the outer volume, this inner volume is now undetectable. Concerns have, however, been raised for the level of plausible deniability in hiding information this way – the contents of the "outer" container filesystem (in particular the access or modification timestamps on the data stored) could raise suspicions as a result of being frozen in its initial state to prevent the user from corrupting the hidden volume. This problem can be eliminated by instructing the system not to protect the hidden volume, although this could result in lost data. FreeOTFE and BestCrypt can have many hidden volumes in a container; TrueCrypt is limited to one hidden volume.

Needless to say, insecure block ciphers or pseudorandom number generators can make it possible to compromise the deniability of such filesystems. To escape the assumption that the used pseudorandom number generation is cryptographically secure, it has been advised to instead fill the encrypted space with pseudorandom data which has itself been encrypted, thus being protected by a separate encryption key since encrypted data is impossible to differentiate from encrypted data In addition to that, the flawed use of block cipher modes of operation can also compromise the cipher algorithm due to watermarking attacks.

Deep Crack

In cryptography, the EFF DES cracker (nicknamed "Deep Crack") is a machine built by the Electronic Frontier Foundation (EFF) in 1998 to perform a brute force search of DES cipher's key space — that is, to decrypt an encrypted message by trying every possible key. The aim in doing this was to prove that DES's key is not long enough to be secure.

DES uses a 56-bit key, meaning that there are 2^56 possible keys under which a message can be encrypted. This is exactly 72,057,594,037,927,936, or approximately 72 quadrillion, possible keys. When DES was approved as a federal standard in 1976, a machine fast enough to test that many keys in a reasonable time would have cost an unreasonable amount of money to build.

Deep Crack was designed by Cryptography Research, Inc., Advanced Wireless Technologies and the EFF. The principal designer was Paul Kocher, president of Cryptography Research. Advanced Wireless Technologies built 1856 custom ASIC DES chips (called Deep Crack or AWT-4500), housed on 29 circuit boards of 64 chips each. The boards were then fitted in six cabinets and mounted in a Sun-4/470 chasis. The search was coordinated by a single PC which assigned ranges of keys to the chips. The entire machine was capable of testing over 90 billion keys per second. It would take about 9 days to test every possible key at that rate. On average, the correct key would be found in half that time.



In 2006, another custom hardware attack machine was designed based on FPGAs. COPACOBANA (COst-optimized PArallel COdeBreaker) shows a similar performance as Deep Crack at considerably lower cost. This advantage is mainly due to progress in IC technology.

Since DES was a federal standard, the US government encouraged the use of DES for all non-classified data. RSA Security wished to demonstrate that DES's key length was not enough to ensure security, so they set up the DES Challenges in 1997, offering a monetary prize. The first DES Challenge was solved in 96 days by the DESCHALL Project led by Rocke Verser in Loveland, Colorado. RSA Security set up DES Challenge II-1, which was solved by distributed.net in 41 days in January and February 1998.





In 1998, the EFF built Deep Crack for less than $250,000. In response to DES Challenge II-2, on July 17, 1998, Deep Crack decrypted a DES-encrypted message after only 56 hours of work, winning $10,000. This was the final blow to DES, against which there were already some published cryptanalytic attacks. The brute force attack showed that cracking DES was actually a very practical proposition. For well-endowed governments or corporations, building a machine like Deep Crack would be no problem.

Six months later, in response to RSA Security's DES Challenge III, and in collaboration with distributed.net, the EFF used Deep Crack to decrypt another DES-encrypted message, winning another $10,000. This time, the operation took less than a day — 22 hours and 15 minutes. The decryption was completed on January 19, 1999. In October of that year, DES was reaffirmed as a federal standard, but this time the standard recommended Triple DES (also referred to as 3DES or TDES).

The small key-space of DES, and relatively high computational costs of triple DES resulted in its replacement by AES as a Federal standard, effective May 26, 2002.

One-time pad

In cryptography, the one-time pad (OTP) is an encryption algorithm where the plaintext is combined with a random key or "pad" that is as long as the plaintext and used only once. A modular addition is used to combine the plaintext with the pad. (For binary data, the operation XOR amounts to the same thing.) It was invented in 1917 and patented a couple of years later. If the key is truly random, never reused, and kept secret, the one-time pad provides perfect secrecy. It has also been proven that any cipher with perfect secrecy must use keys with the same requirements as OTP keys. The key normally consists of a random stream of numbers, each of which indicates the number of places in the alphabet (or number stream, if the plaintext message is in numerical form) which the corresponding letter or number in the plaintext message should be shifted. For messages in the Latin alphabet, for example, the key will consist of a random string of numbers between 0 and 25; for binary messages the key will consist of a random string of 0s and 1s; and so on.

The "pad" part of the name comes from early implementations where the key material was distributed as a pad of paper, so the top sheet could be easily torn off and destroyed after use. For easy concealment, the pad was sometimes reduced to such a small size that a powerful magnifying glass was required to use it. Photos accessible on the Internet show captured KGB pads that fit in the palm of one's hand, or in a walnut shell. To increase security, one-time-pads were sometimes printed onto sheets of highly flammable nitrocellulose.

The one-time pad is derived from the Vernam cipher, named after Gilbert Vernam, one of its inventors. Vernam's system was a cipher that combined a message with a key read from a paper tape loop. In its original form, Vernam's system was not unbreakable because the key could be reused. One-time use came a little later when Joseph Mauborgne recognized that if the key tape was totally random, cryptanalytic difficulty would be increased.

There is some term ambiguity due to the fact that some authors use the term "Vernam cipher" synonymously for the "one-time-pad", while others refer to any additive stream cipher as a "Vernam cipher", including those based on a cryptographically secure pseudorandom number generator (CSPRNG).

HMAC

RFC 2104 HMAC: Keyed-Hashing for Message Authentication

HMAC Algorithm in Detail

In cryptography, a keyed-Hash Message Authentication Code, or HMAC, is a type of message authentication code (MAC) calculated using a specific algorithm involving a cryptographic hash function in combination with a secret key. As with any MAC, it may be used to simultaneously verify both the data integrity and the authenticity of a message. Any iterative cryptographic hash function, such as MD5 or SHA-1, may be used in the calculation of an HMAC; the resulting MAC algorithm is termed HMAC-MD5 or HMAC-SHA-1 accordingly. The cryptographic strength of the HMAC depends upon the cryptographic strength of the underlying hash function, on the size and quality of the key and the size of the hash output length in bits.

An iterative hash function breaks up a message into blocks of a fixed size and iterates over them with a compression function. For example, MD5 and SHA-1 operate on 512-bit blocks. The size of the output of HMAC is the same as that of the underlying hash function (128 or 160 bits in the case of MD5 and SHA-1), although it can be truncated if desired. Truncating the hash image reduces the security of the MAC which is upper bound by the birthday attack.


where h is a cryptographic hash function, K is a secret key padded with extra zeros to the block size of the hash function, m is the message to be authenticated, ∥ denotes concatenation, ⊕ denotes exclusive or (XOR), and the outer padding opad = 0x5c5c5c...5c5c and inner padding ipad = 0x363636...3636 are two one-block–long hexadecimal constants.


The construction and analysis of HMACs was first published in 1996 by Mihir Bellare, Ran Canetti, and Hugo Krawczyk, who also wrote RFC 2104. FIPS PUB 198 generalizes and standardizes the use of HMACs. HMAC-SHA-1 and HMAC-MD5 are used within the IPsec and TLS protocols.


The following pseudocode demonstrates how HMAC may be implemented.

function hmac (key, message)
opad = [0x5c * blocksize] // Where blocksize is that of the underlying hash function
ipad = [0x36 * blocksize]

if (length(key) < blocksize) then
key = key || [0x00 * (blocksize - length(key))] // Pad the key if shorter than blocksize
end if

for i from 0 to length(key) - 1 step 1
ipad[i] = ipad[i] XOR key[i]
opad[i] = opad[i] XOR key[i]
end for

return hash(opad || hash(ipad || message)) // Where || is concatenation
end function

Advanced Encryption Standard

AES

In cryptography, the Advanced Encryption Standard (AES), also known as Rijndael, is a block cipher adopted as an encryption standard by the U.S. government. It has been analyzed extensively and is now used widely worldwide as was the case with its predecessor, the Data Encryption Standard (DES). AES was announced by National Institute of Standards and Technology (NIST) as U.S. FIPS PUB 197 (FIPS 197) on November 26, 2001 after a 5-year standardization process (see Advanced Encryption Standard process for more details). It became effective as a standard May 26, 2002. As of 2006, AES is one of the most popular algorithms used in symmetric key cryptography. It is available by choice in many different encryption packages.

The cipher was developed by two Belgian cryptographers, Joan Daemen and Vincent Rijmen, and submitted to the AES selection process under the name "Rijndael", a portmanteau of the names of the inventors.

As of 2006, the only successful attacks against AES have been side channel attacks. The National Security Agency (NSA) reviewed all the AES finalists, including Rijndael, and stated that all of them were secure enough for US Government non-classified data. In June 2003, the US Government announced that AES may be used for classified information:

"The design and strength of all key lengths of the AES algorithm (i.e., 128, 192 and 256) are sufficient to protect classified information up to the SECRET level. TOP SECRET information will require use of either the 192 or 256 key lengths. The implementation of AES in products intended to protect national security systems and/or information must be reviewed and certified by NSA prior to their acquisition and use."

This marks the first time that the public has had access to a cipher approved by NSA for encryption of TOP SECRET information. Many public products use 128-bit secret keys by default; it is possible that NSA suspects a fundamental weakness in keys this short, or they may simply prefer a safety margin for top secret documents (which may require security decades into the future).

The SHA Hash Functions

SHA1search.com

RSA Wikipedia

Electronic Frontier Foundation

The SHA hash functions are five cryptographic hash functions designed by the National Security Agency (NSA) and published by the NIST as a U.S. Federal Information Processing Standard. SHA stands for Secure Hash Algorithm. Hash algorithms compute a fixed-length digital representation (known as a message digest) of an input data sequence (the message) of any length. They are called “secure” when (in the words of the standard), “it is computationally infeasible to:

   1. find a message that corresponds to a given message digest, or
   2. find two different messages that produce the same message digest.

Any change to a message will, with a very high probability, result in a different message digest.”

The five algorithms are denoted SHA-1, SHA-224, SHA-256, SHA-384, and SHA-512. The latter four variants are sometimes collectively referred to as SHA-2. SHA-1 produces a message digest that is 160 bits long; the number in the other four algorithms' names denote the bit length of the digest they produce.

SHA-1 is employed in several widely used security applications and protocols, including TLS and SSL, PGP, SSH, S/MIME, and IPsec. It was considered to be the successor to MD5, an earlier, widely-used hash function.

The security of SHA-1 has been somewhat compromised by cryptography researchers. Although no attacks have yet been reported on the SHA-2 variants, they are algorithmically similar to SHA-1 and so efforts are underway to develop improved alternative hashing algorithms. "NIST is initiating an effort to develop one or more additional hash algorithms through a public competition, similar to the development process for the Advanced Encryption Standard (AES)." It's tentatively scheduled to proclaim winner and publish final standard in 2012.

Even a small change in the message will, with overwhelming probability, result in a completely different hash due to the avalanche effect.

SHA1("The quick brown fox jumps over the lazy dog")
  = 2fd4e1c6 7a2d28fc ed849ee1 bb76e739 1b93eb12

SHA1("The quick brown fox jumps over the lazy cog")
  = de9f2c7f d25e1b3a fad3e85a 0bd17d9b 100db4b3