SRP - Secure Remote Password

The Secure Remote Password protocol (SRP) is a secure password-based authentication and key-exchange protocol. It solves the problem of authenticating clients to servers securely, in cases where the user of the client software must memorize a small secret (like a password or a passphrase) and where the server carries a verifier for each user, which allows it to authenticate the client but which, if compromised, would not allow the attacker to impersonate the client. In addition, SRP exchanges a cryptographically-strong secret as a byproduct of successful authentication, which enables the two parties to communicate securely.

SRP offers a number of new benefits for password system implementors:

• An attacker with neither the user’s password nor the host’s password file cannot mount a dictionary attack on the password.
• An attacker who captures the host’s password file cannot directly compromise user-to-host authentication and gain access to the host without an expensive dictionary search.
• An attacker who compromises the host does not obtain the the password from a legitimate authentication attempt.
• An attacker who captures the session key cannot use it to mount a dictionary attack on the password.

It is believed that this set of properties is at or near the theoretical limit of security that can be offered by a purely password-based protocol. SRP, which bases its security on the difficulty of solving the Diffie-Hellman problem in the multiplicative field modulo a large safe prime, meets these requirements and does so using only one exponential key exchange round, making it useful for applications in which good performance is an issue. SRP’s security, simplicity, and speed make it ideal for a wide range of real-world applications in which secure password authentication is required. Further technical details of the actual protocol design are available from the Stanford SRP Authentication Project website.

• n - A large prime number
• g - A primitive root modulo n (often called a generator)
• I - The user’s identifier or username
• s - A random string used as the user’s salt
• P - The user’s password
• x - A private key derived from the password and salt
• v - The host’s password verifier
• u - Random scrambling parameter, publicly revealed
• a, b - Ephemeral private keys, generated randomly and not publicly revealed
• A, B - Corresponding public keys
• H( ) - One-way hash function
• K - Session key

The values n and g are well-known values, agreed to beforehand.

The seven steps of SRP-6, from SRP-6: Improvements and Refinements to the Secure Remote Password Protocol by Thomas Wu.

Notes on Clipperz’s implementation

Coming soon …

AES - Advanced Encryption Standard

The Advanced Encryption Standard (AES), also known as Rijndael, is a block cipher adopted as an encryption standard by the US government. AES was announced by National Institute of Standards and Technology (NIST) as US FIPS PUB 197 November 26 2001 after a 5-year standardization process. It became effective as a standard May 26, 2002.

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 comprising the names of the inventors.

Vincent Rijmen and Joan Daemen.
Photo from the PowerBasic Crypto Archive.

Unlike its predecessor DES, Rijndael is a substitution-permutation network, not a Feistel network. AES is fast in both software and hardware, is relatively easy to implement, and requires little memory. As of 2006, AES is one of the most popular algorithms used in symmetric key cryptography.

AES has a fixed block size of 128 bits and a key size of 128, 192 or 256 bits. The key is expanded into a number of separate round keys using special key schedule known as the Rijndael key schedule. Most of AES calculations are done in a special finite field. AES operates on a 4×4 array of bytes, termed the state. For encryption, each round of AES (except the last round) consists of four stages:

1. AddRoundKey — each byte of the state is combined with the round key; each round key is derived from the cipher key using a key schedule.
2. SubBytes — a non-linear substitution step where each byte is replaced with another according to a lookup table.
3. ShiftRows — a transposition step where each row of the state is shifted cyclically a certain number of steps.
4. MixColumns — a mixing operation which operates on the columns of the state, combining the four bytes in each column using a linear transformation.

The final round replaces the MixColumns stage with another instance of AddRoundKey.

Diagram from A Cryptographic Compendium by John Savard.

As of 2006, the only successful attacks against AES have been side channel attacks, not attacking the underlying cipher, but the implementations of the cipher on systems which inadvertently leak 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.”

Notes on Clipperz’s implementation

• Key size: 256 bits
• Cipher mode: CTR

SHA-2 - Secure Hash Algorithms

The SHA (Secure Hash Algorithm) family is a set of related cryptographic hash functions developed by NSA and standardized by NIST (pdf).

This standard specifies four secure hash algorithms, SHA-1, SHA-256, SHA-384, and SHA-512. All four of the algorithms are iterative, one-way hash functions that can process a message to produce a condensed representation called a message digest. These algorithms enable the determination of a message’s integrity: any change to the message will, with a very high probability, result in a different message digest. This property is useful in the generation and verification of digital signatures and message authentication codes, and in the generation of random numbers.

Each algorithm can be described in two stages: preprocessing and hash computation. Preprocessing involves padding a message, parsing the padded message into m-bit blocks, and setting initialization values to be used in the hash computation. The hash computation generates a message schedule from the padded message and uses that schedule, along with functions, constants, and word operations to iteratively generate a series of hash values. The final hash value generated by the hash computation is used to determine the message digest.

Diagram of the iterated hash function structure.
From A Cryptographic Compendium by John Savard.

Diagram of the compression function.
From A Cryptographic Compendium by John Savard.

Notes on Clipperz’s implementation

In order obtain the 128-bit security level and eliminate some weaknesses due to the iterative nature of the SHA family, the hash function used throughout Clipperz is

• SHA_d-256(m) = SHA-256(SHA-256(m))

where SHA-256 is the member of the SHA family with a 256-bit output and m is an arbitrary length message.

This solution is computationally expensive, but it solves both the length extension problem and the partial-message collision issue that afflict SHA algorithms.

ECC- Elliptic Curve Cryptography

Elliptic curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. Elliptic curve cryptography (ECC) was first proposed in 1985 independently by Victor Miller and Neal Koblitz.

Public key cryptography is based on the creation of mathematical puzzles that are difficult to solve without certain knowledge about how they were created. The creator keeps that knowledge secret (the private key) and publishes the puzzle (the public key). The puzzle can then be used to scramble a message in a way that only the creator can unscramble.

Early public key systems, such as the RSA algorithm, used products of two large prime numbers as the puzzle: a user picks two large random primes as her private key, and publishes their product as her public key. The difficulty of factoring ensures that no one else can derive the private key (i.e., the two prime factors) from the public one. However, due to recent progress in factoring, RSA public keys must now be thousands of bits long to provide adequate security.

Another class of puzzle involves solving the equation ab = c for b when a and c are known. Such equations involving real or complex numbers are easily solved using logarithms. However, in a large finite group, finding solutions to such equations is quite difficult and is known as the discrete logarithm problem.

An elliptic curve is a plane curve defined by an equation of the form

y² = x³ + ax + b

The set of points on such a curve can be shown to form an abelian group (with the point at infinity as identity element). If the coordinates x and y are chosen from a large finite field, the solutions of the equation form a finite abelian group.

Elliptic curve multiplication - Diagram from Certicom ECC Tutorial.

The discrete logarithm problem on such elliptic curve groups is believed to be more difficult than the corresponding problem in (the multiplicative group of nonzero elements of) the underlying finite field. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

The U.S. National Security Agency has endorsed ECC technology by including it in its Suite B set of recommended algorithms. You can read more here.

PRNG - Fortuna algorithm

Fortuna is a cryptographically secure pseudo-random number generator (PRNG) devised by Bruce Schneier and Niels Ferguson while writing the book Practical Cryptography. It is named for Fortuna, the Roman goddess of chance.

More precisely, Fortuna is a family of secure PRNGs; its design leaves some choices open to implementors. It is composed of the following pieces:

• The generator itself, which once seeded will produce an indefinite quantity of pseudo-random data.
• The entropy accumulator, which collects genuinely random data from various sources and uses it to reseed the generator when enough new randomness has arrived.
• The seed file, which stores enough state to enable the computer to start generating random numbers as soon as it has booted.

The generator is based on any good block cipher. suggests AES, Serpent or Twofish. The basic idea is to run the cipher in counter mode, encrypting successive values of an incrementing counter. On its own, this would produce statistically identifiable deviations from randomness; for instance, repeated blocks would be generated. Therefore, the key is changed periodically: no more than 1MB of data is generated without a key change. The key is also changed after every data request (however small), so that a key compromise doesn’t endanger old PRNG outputs.

The entropy accumulator is designed to be resistant against “injection” attacks, without needing sophisticated and inevitably unreliable estimators of entropy.

There are 32 “pools” of entropy; each entropy source distributes its alleged entropy evenly over the pools; and on the n^th reseeding of the generator, pool k is used only if 2^k divides n. Thus, the k^th pool is used only 1/2^k of the times. Higher-numbered pools, in other words,

1. contribute to reseedings less frequently;
2. collect a larger amount of entropy between reseedings.

Reseeding is performed by hashing the specified entropy pools into the block cipher’s key.

Unless an attacker is able to control all the sources of alleged entropy flowing into the system, there will be some k for which the k^th pool collects enough entropy between reseedings that a reseeding with that pool ensures security. And that pool will be used at an interval proportional to the amount of entropy in question. Therefore, the system will always recover from an injection attack, and the time it takes to do so is at most a constant factor greater than the theoretical time it could take if we were able to identify which sources of entropy were corrupt and which not.

Fortuna uses 32 pools, and restricts reseeding to happen at most 10 times per second. Running out of pools would then take about 13 years, which Ferguson and Schneier deem long enough for practical purposes. More paranoid implementors, or ones requiring the generation of random data at a colossal rate and correspondingly frequent reseeding, could use a larger number of pools.

Notes on Clipperz’s implementation

Coming soon …

SSSS - Shamir Secret Sharing Scheme

In cryptography, secret sharing refers to any method for distributing a secret amongst a group of participants, each of which is allocated a share of the secret. The secret can only be reconstructed when the shares are combined together; individual shares are of no use on their own.

More formally, in a secret sharing scheme there is one dealer and n players. The dealer gives a secret to the players, but only when specific conditions are fulfilled. The dealer accomplishes this by giving each player a share in such a way that any group of m or more players can together reconstruct the secret but no group of less than m players can. Such a system is called a threshold scheme.

Clipperz adopts Shamir’s secret sharing scheme (SSSS) that was invented by both Adi Shamir (of RSA fame) and George Blakley independently in 1979.

Prof. Adi Shamir, Weizmann Institute of Science

SSSS is based on polynomial interpolation. To allow any m out of n people to construct a given secret, an (m-1)-degree polynomial

f(x) = a₀ + a₁x + … + a_m-1x^m-1

over the finite field GF(q) is constructed such that the coefficient a₀ is the secret and all other coefficients are random elements in the field; the field is known to all participants. Each of the n shares is a pair (x_i, y_i) of numbers satisfying f(x_i) = y_i and x_i > 0. Given any m shares, the polynomial is uniquely determined and hence the secret a₀ can be computed via Lagrange interpolation. However, given m-1 or fewer shares, the secret can be any element in the field.

Shamir’s secret sharing scheme where m = 2 - Diagram from RSA Security Inc.

Shamir’s scheme minimizes the need for random numbers: for every bit in the secret, the dealer must generate t random bits, where t is the threshold number of people.

Notes on Clipperz’s implementation

Coming soon …