NAME

setupDESstate, des_key_setup, block_cipher, desCBCencrypt, desCBCdecrypt, desECBencrypt, desECBdecrypt, des3CBCencrypt, des3CBCdecrypt, des3ECBencrypt, des3ECBdecrypt, key_setup, des56to64, des64to56, setupDES3state, triple_block_cipher, md4, md5, sha1, hmac_md5, hmac_sha1, dec64, enc64, dec32, enc32, genrandom, prng, genprime, gensafeprime, genstrongprime, DSAprimes, probably_prime, smallprimetest, setupRC4state, rc4, rc4skip, rc4back, crtpre, crtin, crtout, crtprefree, crtresfree, rsagen, rsaencrypt, rsadecrypt, rsaalloc, rsafree, rsapuballoc, rsapubfree, rsaprivalloc, rsaprivfree, rsaprivtopub, eggen, egencrypt, egdecrypt, egsign, egverify, egalloc, egfree, egpuballoc, egpubfree, egprivalloc, egprivfree, egsigalloc, egsigfree, egprivtopub − cryptographic security library

SYNOPSIS

­#include <u.h>
­#include <libc.h>
­#include <mp.h>
­#include <libsec.h>

voiddes_key_setup(uchar key[8], ulong schedule[32]);

voidblock_cipher(ulong ∗schedule, uchar ∗data, int decrypting);

voidsetupDESstate(DESstate ∗s, uchar key[8], uchar ∗ivec);

voiddesCBCencrypt(uchar∗, int, DESstate∗);

voiddesCBCdecrypt(uchar∗, int, DESstate∗);

voiddesECBencrypt(uchar∗, int, DESstate∗);

voiddesECBdecrypt(uchar∗, int, DESstate∗);

voidtriple_block_cipher(ulong keys[3][32], uchar∗, int);

voidsetupDES3state(DES3state ∗s, uchar key[3][8], uchar ∗ivec);

voiddes3CBCencrypt(uchar∗, int, DES3state∗);

voiddes3CBCdecrypt(uchar∗, int, DES3state∗);

voiddes3ECBencrypt(uchar∗, int, DES3state∗);

voiddes3ECBdecrypt(uchar∗, int, DES3state∗);

voidkey_setup(uchar[7], ulong[32]);

voiddes56to64(uchar ∗k56, uchar ∗k64);

voiddes64to56(uchar ∗k64, uchar ∗k56);

DigestState∗md4(uchar ∗data, ulong dlen, uchar ∗digest, DigestState ∗state);

DigestState∗md5(uchar ∗data, ulong dlen, uchar ∗digest, DigestState ∗state);

DigestState∗sha1(uchar ∗data, ulong dlen, uchar ∗digest, DigestState ∗state);

DigestState∗hmac_md5(uchar ∗data, ulong dlen,
uchar ∗key, ulong klen,
uchar ∗digest, DigestState ∗state);

DigestState∗hmac_sha1(uchar ∗data, ulong dlen,
uchar ∗key, ulong klen,
uchar ∗digest, DigestState ∗state);

voidsetupRC4state(RC4state ∗s, uchar ∗seed, int slen);

voidrc4(RC4state ∗s, uchar ∗data, int dlen);

voidrc4skip(RC4state ∗s, int nbytes);

voidrc4back(RC4state ∗s, int nbytes);

RSApriv∗rsagen(int nlen, int elen, int nrep);

mpint∗rsaencrypt(RSApub ∗k, mpint ∗in, mpint ∗out);

mpint∗rsadecrypt(RSApriv ∗k, mpint ∗in, mpint ∗out);

RSApub∗rsapuballoc(void);

voidrsapubfree(RSApub∗);

RSApriv∗rsaprivalloc(void);

voidrsaprivfree(RSApriv∗);

RSApub∗rsaprivtopub(RSApriv∗);

EGpriv∗eggen(int nlen, int nrep);

mpint∗egencrypt(EGpub ∗k, mpint ∗in, mpint ∗out);

mpint∗egdecrypt(EGpriv ∗k, mpint ∗in, mpint ∗out);

EGsig∗egsign(EGpriv ∗k, mpint ∗m);

integverify(EGpub ∗k, EGsig ∗sig, mpint ∗m);

EGpub∗egpuballoc(void);

voidegpubfree(EGpub∗);

EGpriv∗egprivalloc(void);

voidegprivfree(EGpriv∗);

EGsig∗egsigalloc(void);

voidegsigfree(EGsig∗);

EGpub∗egprivtopub(EGpriv∗);

intdec64(uchar ∗out, int lim, char ∗in, int n);

intenc64(char ∗out, int lim, uchar ∗in, int n);

intdec32(uchar ∗out, int lim, char ∗in, int n);

intenc32(char ∗out, int lim, uchar ∗in, int n);

voidgenrandom(uchar ∗buf, int nbytes);

voidprng(uchar ∗buf, int nbytes);

intsmallprimetest(mpint ∗p);

intprobably_prime(mpint ∗p, int nrep);

voidgenprime(mpint ∗p, int n, int nrep);

voidgensafeprime(mpint ∗p, mpint ∗alpha, int n, int accuracy);

voidgenstrongprime(mpint ∗p, int n, int nrep);

voidDSAprimes(mpint ∗q, mpint ∗p, uchar seed[SHA1dlen]);

DESCRIPTION

These routines provide a base for cryptographic security. 

DES

The Digital Encryption Standard (DES) has the most functions.  It is a shared key or symmetric encryption using either a 56 bit key for single DES or three 56 bit keys for triple des.  The keys are encoded into 64 bits where every eight bit is parity. 

The basic DES function, block_cipher, works on a block of 8 bytes, converting them in place. It takes a key schedule, a pointer to the block, and a flag indicating encrypting (0) or decrypting (1). The key schedule is created from the key using des_key_setup.

Since it is a bit awkward, ­block_cipher is rarely called directly.  Instead, one normally uses routines that encrypt larger buffers of data and which may chain the encryption state from one buffer to the next.  These routines keep track of the state of the encryption using a ­DESstate structure that contains the key schedule and any chained state.  ­SetupDESstate sets up the ­DESstate structure using the key and an 8 byte initialization vector. 

Electronic code book, using ­desECBencrypt and desECBdecrypt, is the less secure mode.  The encryption of each 8 bytes does not depend on the encryption of any other. Hence the encryption is a substitution cipher using 64 bit characters.

Cipher block chaining mode, using ­desCBCencrypt and desCBCdecrypt, is more secure.  Every block encrypted depends on the initialization vector and all blocks encrypted before it.

For both CBC and ECB modes, a stream of data can be encrypted as multiple buffers.  However, all buffers except the last must be a multiple of 8 bytes to ensure successful decryption of the stream. 

There are equivalent triple DES functions for each of the DES functions. 

In the past Plan 9 used a 56 bit or 7 byte format for DES keys.  To be compatible with the rest of the world, we’ve abandoned this format.  There are two functions: ­des56to64 and ­des64to56 to convert back and forth between the two formats.  Also a key schedule can be set up from the 7 byte format using key_setup.

Secure Hashes

We support several secure hash functions.  The output of the hash is called a digest. A hash is secure if, given the hashed data and the digest, it is difficult to predict the change to the digest resulting from some change to the data without rehashing the whole data.  Therefore, if a secret is part of the hashed data, the digest can be used as an integrity check of the data by anyone possessing the secret.

The routines md4, md5, sha1, hmac_md5, and ­hmac_sha1 differ only in the length of the resulting digest and in the security of the hash.  Usage for each is the same.  The first call to the routine should have ­nil as the ­state parameter.  This call returns a state which can be used to chain subsequent calls.  The last call should have digest non-nil.  ­Digest must point to a buffer of at least the size of the digest produced.  This last call will free the state and copy the result into digest. For example, to hash a single buffer using md5:

 uchar digest[MD5dlen];
 md5(data, len, digest, nil);

To chain a number of buffers together, bounded on each end by some secret:

 char buf[256];
uchar digest[MD5dlen];
DigestState ∗s;
 s = md5("my password", 11, nil, nil);
while((n = read(fd, buf, 256)) > 0)
md5(buf, n, nil, s);
md5("drowssap ym", 11, digest, s);

The constants MD4dlen, MD5dlen, and ­SHA1dlen define the lengths of the digests. 

­Hmac_md5 and ­hmac_sha1 are used slightly differently.  These hash algorithms are keyed and require a key to be specified on every call.  The digest lengths for these hashes are ­MD5dlen and ­SHA1dlen respectively. 

Alleged RC4

This is an algorithm alleged to be Rivest’s RC4 encryption function.  It is a pseudo-random number generator with a 256 byte state and a long cycle.  The input buffer is XOR’d with the output of the generator both to encrypt and to decrypt.  The seed, entered using setupRC4state, can be any length.  The generator can be run forward using rc4, skip over bytes using ­rc4skip to account lost transmissions, or run backwards using ­rc4back to cover retransmitted data.  The ­RC4state structure keeps track of the algorithm. 

RSA

RSA is a public key encryption algorithm.  The owner of a key publishes the public part of the key:

struct RSApub
{
mpint∗n;// modulus
mpint∗ek;// exp (encryption key)
};

This part can be used for encrypting data (with rsaencrypt) to be sent to the owner. The owner decrypts (with rsadecrypt) using his private key:

struct RSApriv
{
RSApubpub;
mpint∗dk;// exp (decryption key)

// precomputed crt values
mpint∗p;
mpint∗q;
mpint∗kp;// k mod p-1
mpint∗kq;// k mod q-1
mpint∗c2;// for converting residues to number
};

Keys are generated using rsagen. ­Rsagen takes both bit length of the modulus, the bit length of the public key exponent, and the number of repetitions of the miller-rabin primality test to run.  If the latter is 0, it does the default number of rounds.  ­Rsagen returns a newly allocated structure containing both public and private keys.  ­Rsaprivtopub returns a newly allocated copy of the public key corresponding to the private key. 

The routines rsaalloc, rsafree, rsapuballoc, rsapubfree, rsaprivalloc, and ­rsaprivfree are provided to aid in user provided key I/O. 

ElGamal

The corresponding keys for the ElGamal algorithm are:

struct EGpub
{
mpint∗p;// modulus
mpint∗alpha;// generator
mpint∗key;// (encryption key) alpha∗∗secret mod p
};

and

struct EGpriv
{
EGpubpub;
mpint∗secret; // (decryption key)
};

­Egsign signs message ­m using a private key ­k yielding a

struct EGsig
{
mpint∗r, ∗s;
};

­Egverify returns 0 if the signature is valid and −1 if not. 

Encodings

Two readable and 7-bit safe encodings exist for binary data; base 64 and base 32.  Base 64 is the more compact and more popular, used by MIME and HTTP.  Base 32 is preferred when human transmission is involved.  It avoids confusion by not including upper case or ’0’, ’o’, ’1’, and ’l’ in its character set.  Base 64 can encode buffers of any length while base 32 only works on buffers a multiple of 5 bytes long. 

­Enc32 and ­enc64 both create null terminated strings.  They return the size of the encoded string (without the null) or -1 if the encoding fails.  The encoding fails if lim, the length of the output buffer, is too small.  Also, for base 32, the encoding fails if the input buffer length, n, is not a multiple of 5.

­Dec32 and ­dec64 return the number of bytes decoded or -1 if the decoding fails.  The decoding fails if the output buffer is not large enough or, for base 32, if the input buffer length is not a multiple of 8. 

Random numbers

Most security software requires a source of random or, at the very least, unguessable numbers. 

­Genrandom fills a buffer with bytes from the X9.17 pseudo-random number generator.  The X9.17 generator is seeded by 24 truly random bytes read from /dev/random. 

­Prng uses the native rand(2) pseudo-random number generator to fill the buffer.  Used with srand, this function can produce a reproducible stream of pseudo random numbers useful in testing.

Both functions may be passed to ­mprand (see mp(2)).

Prime numbers

Public key algorithms abound in prime numbers.  The following routines generate primes or test numbers for primality. 

­Smallprimetest checks for divisibility by the first 10000 primes.  It returns 0 if ­p is not divisible by the primes and −1 if it is. 

­Probably_prime uses the Miller-Rabin test to test p. It returns non-zero if ­P is probably prime.  The probability of it not being prime is 1/4∗∗nrep. 

­Genprime generates a random ­n bit prime.  Since it uses the Miller-Rabin test, ­nrep is the repetition count passed to probably_prime. ­Gensafegprime generates an n-bit prime ­p and a generator ­alpha of the multiplicative group of integers mod p; there is a prime q such that p-1=2∗q.  ­Genstrongprime generates a prime, p, with the following properties:

−p-1 has a large prime factor, p’. A large factor is one close to 1/2 the bit length of p.

−p’-1 has a large prime factor

−p+1 has a large prime factor

−(p-1)/2 is prime

­DSAprimes generates two primes, ­q and p, using the NIST recommended algorithm for DSA primes.  ­q divides p-1.

SOURCE

­/sys/src/libsec

SEE ALSO

mp(2)

Plan 9  —  July 29, 2000