iPXE
|
DES algorithm. More...
#include <stdint.h>
#include <string.h>
#include <errno.h>
#include <byteswap.h>
#include <ipxe/rotate.h>
#include <ipxe/crypto.h>
#include <ipxe/ecb.h>
#include <ipxe/cbc.h>
#include <ipxe/init.h>
#include <ipxe/des.h>
Go to the source code of this file.
Data Structures | |
struct | des_generator |
A DES systematic permutation generator. More... | |
Macros | |
#define | DES_SCHEDULE 0x0d556aab |
DES shift schedule. More... | |
#define | SBYTE(x, y) ( ( (y) << 4 ) | (x) ) |
Define an element pair in a DES S-box. More... | |
#define | SBOX(x0, x1, x2, x3, x4, x5, x6, x7, x8, x9, xa, xb, xc, xd, xe, xf, y0, y1, y2, y3, y4, y5, y6, y7, y8, y9, ya, yb, yc, yd, ye, yf) |
Define a row pair in a DES S-box. More... | |
#define | DES_PC2(x) ( (x) + ( ( (x) > 28 ) ? 4 : 0 ) ) |
Define a bit index within permuted choice 2 (PC2) More... | |
#define | DES_PC2R(r1, c3, c2, c1, c0, r0) |
Define six bits of permuted choice 2 (PC2) More... | |
#define | DES_GENERATOR(PERMUTATION, OFFSET, INV5, BIT5, INV4, BIT4, INV3, BIT3, INV2, BIT2, INV1, BIT1, INV0, BIT0) |
Define a DES permutation generator. More... | |
Functions | |
FILE_LICENCE (GPL2_OR_LATER_OR_UBDL) | |
static void | des_generate (struct des_generator *generator) |
Generate DES permutation. More... | |
static void | des_init (void) |
Initialise permutations. More... | |
struct init_fn des_init_fn | __init_fn (INIT_NORMAL) |
Initialisation function. More... | |
static void | des_permute (const uint8_t *permutation, const uint8_t *in, uint8_t *out) |
Perform bit permutation. More... | |
static uint32_t | des_sbox (uint32_t in, const union des_round_key *rkey) |
Perform DES S-box substitution. More... | |
static void | des_round (union des_block *block, const union des_round_key *rkey) |
Perform a single DES round. More... | |
static void | des_rounds (const union des_block *in, union des_block *out, const union des_round_key *rkey, ssize_t offset) |
Perform all DES rounds. More... | |
static uint32_t | des_rol28 (uint32_t dword) |
Rotate 28-bit word. More... | |
static int | des_setkey (void *ctx, const void *key, size_t keylen) |
Set key. More... | |
static void | des_encrypt (void *ctx, const void *src, void *dst, size_t len) |
Encrypt data. More... | |
static void | des_decrypt (void *ctx, const void *src, void *dst, size_t len) |
Decrypt data. More... | |
ECB_CIPHER (des_ecb, des_ecb_algorithm, des_algorithm, struct des_context, DES_BLOCKSIZE) | |
CBC_CIPHER (des_cbc, des_cbc_algorithm, des_algorithm, struct des_context, DES_BLOCKSIZE) | |
Variables | |
static const uint8_t | des_s [8][32] |
DES S-boxes S1..S8. More... | |
static uint8_t | des_pc1c [29] |
DES permuted choice 1 (PC1) "C" register. More... | |
static uint8_t | des_pc1d [33] |
DES permuted choice 1 (PC1) "D" register. More... | |
static const uint8_t | des_pc2 [65] |
DES permuted choice 2 (PC2) More... | |
static uint8_t | des_ip [65] |
DES initial permutation (IP) More... | |
static const uint8_t | des_p [33] |
DES data permutation (P) More... | |
static uint8_t | des_fp [65] |
DES final / inverse initial permutation (FP / IP^-1) More... | |
static struct des_generator | des_generators [] |
DES permutation generators. More... | |
struct cipher_algorithm | des_algorithm |
Basic DES algorithm. More... | |
DES algorithm.
DES was not designed to be implemented in software, and therefore contains a large number of bit permutation operations that are essentially free in hardware (requiring only wires, no gates) but expensive in software.
Since DES is no longer used as a practical block cipher for large volumes of data, we optimise for code size, and do not attempt to obtain fast throughput.
The algorithm is specified in NIST SP 800-67, downloadable from https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-67r2.pdf
Definition in file des.c.
#define DES_SCHEDULE 0x0d556aab |
DES shift schedule.
The DES shift schedule (ordered from round 16 down to round 1) is {1,2,2,2,2,2,2,1,2,2,2,2,2,2,1,1}. In binary, this may be represented as {1,10,10,10,10,10,10,1,10,10,10,10,10,10,1,1} and concatenated (without padding) to produce a single binary integer 1101010101010110101010101011 (equal to 0x0d556aab in hexadecimal).
This integer may then be consumed LSB-first, where a 1 bit indicates a shift and the generation of a round key, and a 0 bit indicates a shift without the generation of a round key.
#define SBYTE | ( | x, | |
y | |||
) | ( ( (y) << 4 ) | (x) ) |
Define an element pair in a DES S-box.
x | Upper element of element pair |
y | Lower element of element pair |
DES S-box elements are 4-bit values. We encode two values per byte, ordering the elements so that the six-bit input value may be used directly as a lookup index.
Specifically, if the input value is {r1,c3,c2,c1,c0,r0}, where {r1,r0} is the table row index and {c3,c2,c1,c0} is the table column index (as used in the DES specification), then:
#define SBOX | ( | x0, | |
x1, | |||
x2, | |||
x3, | |||
x4, | |||
x5, | |||
x6, | |||
x7, | |||
x8, | |||
x9, | |||
xa, | |||
xb, | |||
xc, | |||
xd, | |||
xe, | |||
xf, | |||
y0, | |||
y1, | |||
y2, | |||
y3, | |||
y4, | |||
y5, | |||
y6, | |||
y7, | |||
y8, | |||
y9, | |||
ya, | |||
yb, | |||
yc, | |||
yd, | |||
ye, | |||
yf | |||
) |
Define a row pair in a DES S-box.
x0..xf | Upper row of row pair |
y0..yf | Lower row of row pair |
#define DES_PC2 | ( | x | ) | ( (x) + ( ( (x) > 28 ) ? 4 : 0 ) ) |
Define a bit index within permuted choice 2 (PC2)
bit | Bit index |
Permuted choice 2 (PC2) is used to select bits from a concatenated pair of 28-bit registers ("C" and "D") as part of the key schedule. We store these as 32-bit registers and so must add 4 to indexes above 28.
#define DES_PC2R | ( | r1, | |
c3, | |||
c2, | |||
c1, | |||
c0, | |||
r0 | |||
) |
Define six bits of permuted choice 2 (PC2)
r1:r0 | Bits corresponding to S-box row index |
c3:c0 | Bits corresponding to S-box column index |
There are 8 steps within a DES round (one step per S-box). Each step requires six bits of the round key, corresponding to the S-box input value {r1,c3,c2,c1,c0,r0}, where {r1,r0} is the table row index and {c3,c2,c1,c0} is the table column index.
As an optimisation, we store the least significant of the 6 bits in the sign bit of a signed 8-bit value, and the remaining 5 bits in the least significant 5 bits of the 8-bit value. See the comments in des_sbox() for further details.
#define DES_GENERATOR | ( | PERMUTATION, | |
OFFSET, | |||
INV5, | |||
BIT5, | |||
INV4, | |||
BIT4, | |||
INV3, | |||
BIT3, | |||
INV2, | |||
BIT2, | |||
INV1, | |||
BIT1, | |||
INV0, | |||
BIT0 | |||
) |
Define a DES permutation generator.
PERMUTATION | Permutation |
OFFSET | Fixed input bit offset (0 or 1) |
INV<n> | Input bit index bit <n> should be inverted |
BIT<n> | Source bit for input bit index bit <n> |
generator | Permutation generator |
FILE_LICENCE | ( | GPL2_OR_LATER_OR_UBDL | ) |
|
static |
Generate DES permutation.
generator | Generator |
Definition at line 306 of file des.c.
References bit, DBGC2, DBGC2_HDA, index, des_generator::permutation, ror32(), and des_generator::seed.
Referenced by des_init().
|
static |
Initialise permutations.
Definition at line 360 of file des.c.
References des_generate(), and des_generators.
struct init_fn des_init_fn __init_fn | ( | INIT_NORMAL | ) |
Initialisation function.
Perform bit permutation.
permutation | Bit permutation (zero-terminated) |
in | Input value |
out | Output value |
Definition at line 382 of file des.c.
Referenced by des_round(), des_rounds(), and des_setkey().
|
static |
Perform DES S-box substitution.
in | 32-bit input value (native endian) |
rkey | 48-bit round key |
out | 32-bit output value (native endian) |
Definition at line 409 of file des.c.
References des_s, in, key, out, rol32(), and des_round_key::step.
Referenced by des_round().
|
static |
Perform a single DES round.
block | DES block |
rkey | 48-bit round key |
Definition at line 492 of file des.c.
References be32_to_cpu, block, des_dword::byte, cpu_to_be32, DBGC2, des_p, des_permute(), des_sbox(), des_dword::dword, and des_round_key::dword.
Referenced by des_rounds().
|
static |
Perform all DES rounds.
in | Input DES block |
out | Output DES block |
rkey | Starting 48-bit round key |
offset | Byte offset between round keys |
Definition at line 527 of file des.c.
References be32_to_cpu, DBGC, des_fp, des_ip, des_permute(), des_round(), DES_ROUNDS, in, offset, out, and tmp.
Referenced by des_decrypt(), and des_encrypt().
Rotate 28-bit word.
dword | 28-bit dword value |
dword | Rotated 28-bit dword value |
Definition at line 557 of file des.c.
References be32_to_cpu, cpu_to_be32, and rol32().
Referenced by des_setkey().
|
static |
Set key.
ctx | Context |
key | Key |
keylen | Key length |
rc | Return status code |
Definition at line 586 of file des.c.
References assert(), be32_to_cpu, des_round_key::byte, ctx, DBGC, DBGC2, DBGC_HDA, DES_BLOCKSIZE, des_pc1c, des_pc1d, des_pc2, des_permute(), des_rol28(), DES_ROUNDS, DES_SCHEDULE, des_round_key::dword, EINVAL, key, reg, and des_context::rkey.
|
static |
Encrypt data.
ctx | Context |
src | Data to encrypt |
dst | Buffer for encrypted data |
len | Length of data |
Definition at line 646 of file des.c.
References assert(), ctx, DES_BLOCKSIZE, des_rounds(), len, des_context::rkey, and src.
|
static |
Decrypt data.
ctx | Context |
src | Data to decrypt |
dst | Buffer for decrypted data |
len | Length of data |
Definition at line 664 of file des.c.
References assert(), ctx, DES_BLOCKSIZE, DES_ROUNDS, des_rounds(), len, des_context::rkey, and src.
ECB_CIPHER | ( | des_ecb | , |
des_ecb_algorithm | , | ||
des_algorithm | , | ||
struct des_context | , | ||
DES_BLOCKSIZE | |||
) |
CBC_CIPHER | ( | des_cbc | , |
des_cbc_algorithm | , | ||
des_algorithm | , | ||
struct des_context | , | ||
DES_BLOCKSIZE | |||
) |
|
static |
|
static |
DES permuted choice 1 (PC1) "C" register.
Definition at line 229 of file des.c.
Referenced by des_setkey().
|
static |
DES permuted choice 1 (PC1) "D" register.
Definition at line 232 of file des.c.
Referenced by des_setkey().
|
static |
DES permuted choice 2 (PC2)
Definition at line 235 of file des.c.
Referenced by des_setkey().
|
static |
|
static |
DES data permutation (P)
Definition at line 251 of file des.c.
Referenced by des_round().
|
static |
DES final / inverse initial permutation (FP / IP^-1)
Definition at line 258 of file des.c.
Referenced by des_rounds().
|
static |
DES permutation generators.
Definition at line 261 of file des.c.
Referenced by des_init().
struct cipher_algorithm des_algorithm |
Basic DES algorithm.
Definition at line 676 of file des.c.
Referenced by mschapv2_challenge_response().