* FreeSec crypt()
@ 2012-06-12 23:51 Solar Designer
2012-06-13 1:18 ` Rich Felker
0 siblings, 1 reply; 17+ messages in thread
From: Solar Designer @ 2012-06-12 23:51 UTC (permalink / raw)
To: musl
[-- Attachment #1: Type: text/plain, Size: 596 bytes --]
Rich -
As discussed on IRC, here is a revision of the FreeSec crypt() code with
greatly reduced memory requirements: 10 KB for the "shared" and "local"
structs combined. The original code required about 70 KB of .bss.
This passes the included tests, but more testing is desired - perhaps
fuzz this on random passwords/salts against other implementations.
Also, we could want to add a runtime self-test, which would detect
possible miscompiles.
Oh, and I haven't yet replaced the cast to signed char in ascii_to_bin().
Anyway, this should be better than what's currently in musl.
Alexander
[-- Attachment #2: crypt_freesec.h --]
[-- Type: text/plain, Size: 2990 bytes --]
/*
* The following notice applies to this header file (only):
*
* Copyright (c) 2002,2010,2012 Solar Designer <solar at openwall.com>
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted.
*/
#ifndef _CRYPT_FREESEC_H
#define _CRYPT_FREESEC_H
struct _crypt_extended_shared {
u_int32_t psbox[8][64];
u_int32_t ip_maskl[16][16], ip_maskr[16][16];
u_int32_t fp_maskl[16][16], fp_maskr[16][16];
u_int32_t key_perm_maskl[16][16], key_perm_maskr[16][16];
u_int32_t comp_maskl0[8][8], comp_maskr0[8][8];
u_int32_t comp_maskl1[8][16], comp_maskr1[8][16];
};
struct _crypt_extended_local {
int initialized;
u_int32_t saltbits;
u_int32_t old_salt;
u_int32_t en_keysl[16], en_keysr[16];
u_int32_t old_rawkey0, old_rawkey1;
char output[21];
};
/*
* _crypt_extended_init() must be called explicitly before first use of
* _crypt_extended_r(). Strictly speaking, _crypt_extended_init() is not
* reentrant unless the "shared" struct happens to be private to each call.
* All it does is initialize some variables inside the "shared" struct to
* constant values, so it is unlikely that anything would go wrong if this is
* done multiple times in parallel, but correct behavior in that case is not
* guaranteed (e.g., things may go wrong if a given CPU architecture can't
* operate on 32-bit quantities natively, requiring read-modify-write
* instruction sequences operating on larger quantities and thus affecting
* nearby array elements).
*
* After _crypt_extended_init() has returned, the resulting "shared" struct
* may in fact be safely shared between different threads' calls to
* _crypt_extended_r(), which is in fact reentrant (but each concurrent call
* must use its own instance of the "local" struct).
*
* Before first use of the "local" struct, its "initialized" field must be
* set to 0. This is compatible with the requirement of some other crypt_r()
* implementations requiring their entire data structure to be initialized
* with all zero bytes, so that approach may be applied instead (e.g., this
* may be required from the callers of a wrapper function).
*
* _crypt_extended_r() returns NULL on error. Although modern standards say
* that crypt(3) does in fact return NULL on error, many applications do not
* expect that. Thus, it is recommended that a crypt(3)-like wrapper function
* translate these NULL returns into strings guaranteed to be different from
* the "setting" string, too short for matching a valid password hash, and not
* containing any characters that would be special for the passwd file format.
* Specifically, such a wrapper function may return "*0" on error as long as
* the "setting" string does not start with "*0", or "*1" otherwise.
*/
void _crypt_extended_init(struct _crypt_extended_shared *shared);
char *_crypt_extended_r(const char *key, const char *setting,
const struct _crypt_extended_shared *shared,
struct _crypt_extended_local *local);
#endif
[-- Attachment #3: crypt_freesec.c --]
[-- Type: text/plain, Size: 22515 bytes --]
/*
* This version is derived from the original implementation of FreeSec
* (release 1.1) by David Burren. I've reviewed the changes made in
* OpenBSD (as of 2.7) and modified the original code in a similar way
* where applicable. I've also made it reentrant, reduced its memory
* usage (with only minimal performance impact), and made the handling
* of invalid salts mostly UFC-crypt compatible.
* - Solar Designer <solar at openwall.com>
*/
/*
* FreeSec: libcrypt for NetBSD
*
* Copyright (c) 1994 David Burren
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* 3. Neither the name of the author nor the names of other contributors
* may be used to endorse or promote products derived from this software
* without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*
* $Owl: Owl/packages/glibc/crypt_freesec.c,v 1.6 2010/02/20 14:45:06 solar Exp $
* $Id: crypt.c,v 1.15 1994/09/13 04:58:49 davidb Exp $
*
* This is an original implementation of the DES and the crypt(3) interfaces
* by David Burren <davidb at werj.com.au>.
*
* An excellent reference on the underlying algorithm (and related
* algorithms) is:
*
* B. Schneier, Applied Cryptography: protocols, algorithms,
* and source code in C, John Wiley & Sons, 1994.
*
* Note that in that book's description of DES the lookups for the initial,
* pbox, and final permutations are inverted (this has been brought to the
* attention of the author). A list of errata for this book has been
* posted to the sci.crypt newsgroup by the author and is available for FTP.
*
* ARCHITECTURE ASSUMPTIONS:
* This code used to have some nasty ones, but these have been removed
* by now. The code requires a 32-bit integer type, though.
*/
#include <sys/types.h>
#include <string.h>
#ifdef TEST
#include <stdio.h>
#endif
#include "crypt_freesec.h"
#define _PASSWORD_EFMT1 '_'
static const u_char IP[64] = {
58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20, 12, 4,
62, 54, 46, 38, 30, 22, 14, 6, 64, 56, 48, 40, 32, 24, 16, 8,
57, 49, 41, 33, 25, 17, 9, 1, 59, 51, 43, 35, 27, 19, 11, 3,
61, 53, 45, 37, 29, 21, 13, 5, 63, 55, 47, 39, 31, 23, 15, 7
};
static const u_char key_perm[56] = {
57, 49, 41, 33, 25, 17, 9, 1, 58, 50, 42, 34, 26, 18,
10, 2, 59, 51, 43, 35, 27, 19, 11, 3, 60, 52, 44, 36,
63, 55, 47, 39, 31, 23, 15, 7, 62, 54, 46, 38, 30, 22,
14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 28, 20, 12, 4
};
static const u_char key_shifts[16] = {
1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1
};
static const u_char comp_perm[48] = {
14, 17, 11, 24, 1, 5, 3, 28, 15, 6, 21, 10,
23, 19, 12, 4, 26, 8, 16, 7, 27, 20, 13, 2,
41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48,
44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32
};
/*
* No E box is used, as it's replaced by some ANDs, shifts, and ORs.
*/
static const u_char sbox[8][64] = {
{
14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7,
0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8,
4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0,
15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13
},
{
15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10,
3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5,
0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15,
13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9
},
{
10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8,
13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1,
13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7,
1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12
},
{
7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15,
13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9,
10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4,
3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14
},
{
2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9,
14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6,
4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14,
11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3
},
{
12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11,
10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8,
9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6,
4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13
},
{
4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1,
13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6,
1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2,
6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12
},
{
13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7,
1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2,
7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8,
2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11
}
};
static const u_char pbox[32] = {
16, 7, 20, 21, 29, 12, 28, 17, 1, 15, 23, 26, 5, 18, 31, 10,
2, 8, 24, 14, 32, 27, 3, 9, 19, 13, 30, 6, 22, 11, 4, 25
};
static const u_int32_t bits32[32] =
{
0x80000000, 0x40000000, 0x20000000, 0x10000000,
0x08000000, 0x04000000, 0x02000000, 0x01000000,
0x00800000, 0x00400000, 0x00200000, 0x00100000,
0x00080000, 0x00040000, 0x00020000, 0x00010000,
0x00008000, 0x00004000, 0x00002000, 0x00001000,
0x00000800, 0x00000400, 0x00000200, 0x00000100,
0x00000080, 0x00000040, 0x00000020, 0x00000010,
0x00000008, 0x00000004, 0x00000002, 0x00000001
};
static const u_char bits8[8] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
static const u_char ascii64[] =
"./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
/* 0000000000111111111122222222223333333333444444444455555555556666 */
/* 0123456789012345678901234567890123456789012345678901234567890123 */
/*
* We match the behavior of UFC-crypt on systems where "char" is signed by
* default (the majority), regardless of char's signedness on our system.
*/
static inline int
ascii_to_bin(char ch)
{
signed char sch = ch;
int retval;
retval = sch - '.';
if (sch >= 'A') {
retval = sch - ('A' - 12);
if (sch >= 'a')
retval = sch - ('a' - 38);
}
retval &= 0x3f;
return retval;
}
/*
* When we choose to "support" invalid salts, nevertheless disallow those
* containing characters that would violate the passwd file format.
*/
static inline int
ascii_is_unsafe(char ch)
{
return !ch || ch == '\n' || ch == ':';
}
static void init_ip_k(struct _crypt_extended_shared *shared)
{
int i, j, k, inbit, obit;
u_int32_t il, ir, fl, fr;
const u_int32_t *bits28, *bits24;
u_char inv_key_perm[64];
u_char inv_comp_perm[56];
u_char init_perm[64], final_perm[64];
bits24 = (bits28 = bits32 + 4) + 4;
/*
* Set up the initial & final permutations into a useful form, and
* initialise the inverted key permutation.
*/
for (i = 0; i < 64; i++) {
init_perm[final_perm[i] = IP[i] - 1] = i;
inv_key_perm[i] = 255;
}
/*
* Invert the key permutation and initialise the inverted key
* compression permutation.
*/
for (i = 0; i < 56; i++) {
inv_key_perm[key_perm[i] - 1] = i;
inv_comp_perm[i] = 255;
}
/*
* Invert the key compression permutation.
*/
for (i = 0; i < 48; i++) {
inv_comp_perm[comp_perm[i] - 1] = i;
}
/*
* Set up the OR-mask arrays for the initial and final permutations,
* and for the key initial and compression permutations.
*/
for (k = 0; k < 16; k++) {
for (i = 0; i < 16; i++) {
il = ir = fl = fr = 0;
for (j = 0; j < 4; j++) {
inbit = 4 * k + j;
if (i & bits8[j + 4]) {
if ((obit = init_perm[inbit]) < 32)
il |= bits32[obit];
else
ir |= bits32[obit - 32];
if ((obit = final_perm[inbit]) < 32)
fl |= bits32[obit];
else
fr |= bits32[obit - 32];
}
}
shared->ip_maskl[k][i] = il;
shared->ip_maskr[k][i] = ir;
shared->fp_maskl[k][i] = fl;
shared->fp_maskr[k][i] = fr;
il = ir = 0;
for (j = 0; j < 4 - (k & 1); j++) {
inbit = 4 * k + j;
if (i & bits8[j + 4]) {
if ((obit = inv_key_perm[inbit]) == 255)
continue;
if (obit < 28)
il |= bits28[obit];
else
ir |= bits28[obit - 28];
}
}
shared->key_perm_maskl[k][i] = il;
shared->key_perm_maskr[k][i] = ir;
}
}
for (k = 0; k < 8; k++) {
for (i = 0; i < 8; i++) {
il = ir = 0;
for (j = 0; j < 3; j++) {
inbit = 7 * k + j;
if (i & bits8[j + 5]) {
if ((obit = inv_comp_perm[inbit]) == 255)
continue;
if (obit < 24)
il |= bits24[obit];
else
ir |= bits24[obit - 24];
}
}
shared->comp_maskl0[k][i] = il;
shared->comp_maskr0[k][i] = ir;
}
for (i = 0; i < 16; i++) {
il = ir = 0;
for (j = 3; j < 7; j++) {
inbit = 7 * k + j;
if (i & bits8[j + 1]) {
if ((obit = inv_comp_perm[inbit]) == 255)
continue;
if (obit < 24)
il |= bits24[obit];
else
ir |= bits24[obit - 24];
}
}
shared->comp_maskl1[k][i] = il;
shared->comp_maskr1[k][i] = ir;
}
}
}
static void init_s(struct _crypt_extended_shared *shared)
{
int i, j, b;
u_char u_sbox[8][64];
u_char un_pbox[32];
/*
* Invert the S-boxes, reordering the input bits.
*/
for (i = 0; i < 8; i++)
for (j = 0; j < 64; j++) {
b = (j & 0x20) | ((j & 1) << 4) | ((j >> 1) & 0xf);
u_sbox[i][j] = sbox[i][b];
}
/*
* Invert the P-box permutation, and convert into OR-masks for
* handling the output of the S-box arrays setup above.
*/
for (i = 0; i < 32; i++)
un_pbox[pbox[i] - 1] = i;
for (b = 0; b < 8; b++) {
for (i = 0; i < 64; i++) {
u_int32_t p = 0;
for (j = 0; j < 4; j++) {
if (u_sbox[b][i] & bits8[j + 4])
p |= bits32[un_pbox[4 * b + j]];
}
shared->psbox[b][i] = p;
}
}
}
void
_crypt_extended_init(struct _crypt_extended_shared *shared)
{
init_ip_k(shared);
init_s(shared);
}
static void
des_init_local(struct _crypt_extended_local *local)
{
local->old_rawkey0 = local->old_rawkey1 = 0;
local->saltbits = 0;
local->old_salt = 0;
local->initialized = 1;
}
static void
setup_salt(u_int32_t salt, struct _crypt_extended_local *local)
{
u_int32_t obit, saltbit, saltbits;
int i;
if (salt == local->old_salt)
return;
local->old_salt = salt;
saltbits = 0;
saltbit = 1;
obit = 0x800000;
for (i = 0; i < 24; i++) {
if (salt & saltbit)
saltbits |= obit;
saltbit <<= 1;
obit >>= 1;
}
local->saltbits = saltbits;
}
static int
des_setkey(const u_char *key,
const struct _crypt_extended_shared *shared,
struct _crypt_extended_local *local)
{
u_int32_t k0, k1, rawkey0, rawkey1;
int shifts, round;
rawkey0 =
(u_int32_t)(u_char)key[3] |
((u_int32_t)(u_char)key[2] << 8) |
((u_int32_t)(u_char)key[1] << 16) |
((u_int32_t)(u_char)key[0] << 24);
rawkey1 =
(u_int32_t)(u_char)key[7] |
((u_int32_t)(u_char)key[6] << 8) |
((u_int32_t)(u_char)key[5] << 16) |
((u_int32_t)(u_char)key[4] << 24);
if ((rawkey0 | rawkey1)
&& rawkey0 == local->old_rawkey0
&& rawkey1 == local->old_rawkey1) {
/*
* Already setup for this key.
* This optimisation fails on a zero key (which is weak and
* has bad parity anyway) in order to simplify the starting
* conditions.
*/
return 0;
}
local->old_rawkey0 = rawkey0;
local->old_rawkey1 = rawkey1;
/*
* Do key permutation and split into two 28-bit subkeys.
*/
{
int i, inbit;
k0 = k1 = 0;
for (i = 0, inbit = 28; i < 8; i++, inbit -= 4) {
k0 |= shared->key_perm_maskl[i][(rawkey0 >> inbit) & 0xf] |
shared->key_perm_maskl[i + 8][(rawkey1 >> inbit) & 0xf];
k1 |= shared->key_perm_maskr[i][(rawkey0 >> inbit) & 0xf] |
shared->key_perm_maskr[i + 8][(rawkey1 >> inbit) & 0xf];
}
}
/*
* Rotate subkeys and do compression permutation.
*/
shifts = 0;
for (round = 0; round < 16; round++) {
u_int32_t t0, t1;
shifts += key_shifts[round];
t0 = (k0 << shifts) | (k0 >> (28 - shifts));
t1 = (k1 << shifts) | (k1 >> (28 - shifts));
{
int i, inbit;
u_int32_t kl, kr;
kl = kr = 0;
inbit = 25;
for (i = 0; i < 4; i++) {
kl |= shared->comp_maskl0[i][(t0 >> inbit) & 7] |
shared->comp_maskl0[i + 4][(t1 >> inbit) & 7];
kr |= shared->comp_maskr0[i][(t0 >> inbit) & 7] |
shared->comp_maskr0[i + 4][(t1 >> inbit) & 7];
inbit -= 4;
kl |= shared->comp_maskl1[i][(t0 >> inbit) & 0xf] |
shared->comp_maskl1[i + 4][(t1 >> inbit) & 0xf];
kr |= shared->comp_maskr1[i][(t0 >> inbit) & 0xf] |
shared->comp_maskr1[i + 4][(t1 >> inbit) & 0xf];
inbit -= 3;
}
local->en_keysl[round] = kl;
local->en_keysr[round] = kr;
}
}
return 0;
}
static int
do_des(u_int32_t l_in, u_int32_t r_in, u_int32_t *l_out, u_int32_t *r_out,
int count,
const struct _crypt_extended_shared *shared,
struct _crypt_extended_local *local)
{
/*
* l_in, r_in, l_out, and r_out are in pseudo-"big-endian" format.
*/
u_int32_t l, r, *kl, *kr, *kl1, *kr1;
u_int32_t f, r48l, r48r, saltbits;
int round;
kl1 = local->en_keysl;
kr1 = local->en_keysr;
/*
* Do initial permutation (IP).
*/
l = r = 0;
if (l_in | r_in) {
int i, inbit;
for (i = 0, inbit = 28; i < 8; i++, inbit -= 4) {
l |= shared->ip_maskl[i][(l_in >> inbit) & 0xf] |
shared->ip_maskl[i + 8][(r_in >> inbit) & 0xf];
r |= shared->ip_maskr[i][(l_in >> inbit) & 0xf] |
shared->ip_maskr[i + 8][(r_in >> inbit) & 0xf];
}
}
saltbits = local->saltbits;
while (count--) {
/*
* Do each round.
*/
kl = kl1;
kr = kr1;
round = 16;
while (round--) {
/*
* Expand R to 48 bits (simulate the E-box).
*/
r48l = ((r & 0x00000001) << 23)
| ((r & 0xf8000000) >> 9)
| ((r & 0x1f800000) >> 11)
| ((r & 0x01f80000) >> 13)
| ((r & 0x001f8000) >> 15);
r48r = ((r & 0x0001f800) << 7)
| ((r & 0x00001f80) << 5)
| ((r & 0x000001f8) << 3)
| ((r & 0x0000001f) << 1)
| ((r & 0x80000000) >> 31);
/*
* Do salting for crypt() and friends, and
* XOR with the permuted key.
*/
f = (r48l ^ r48r) & saltbits;
r48l ^= f ^ *kl++;
r48r ^= f ^ *kr++;
/*
* Do S-box lookups (which shrink it back to 32 bits)
* and do the P-box permutation at the same time.
*/
f = shared->psbox[0][r48l >> 18]
| shared->psbox[1][(r48l >> 12) & 0x3f]
| shared->psbox[2][(r48l >> 6) & 0x3f]
| shared->psbox[3][r48l & 0x3f]
| shared->psbox[4][r48r >> 18]
| shared->psbox[5][(r48r >> 12) & 0x3f]
| shared->psbox[6][(r48r >> 6) & 0x3f]
| shared->psbox[7][r48r & 0x3f];
/*
* Now that we've permuted things, complete f().
*/
f ^= l;
l = r;
r = f;
}
r = l;
l = f;
}
/*
* Do final permutation (inverse of IP).
*/
{
int i, inbit;
u_int32_t lo, ro;
lo = ro = 0;
for (i = 0, inbit = 28; i < 8; i++, inbit -= 4) {
lo |= shared->fp_maskl[i][(l >> inbit) & 0xf] |
shared->fp_maskl[i + 8][(r >> inbit) & 0xf];
ro |= shared->fp_maskr[i][(l >> inbit) & 0xf] |
shared->fp_maskr[i + 8][(r >> inbit) & 0xf];
}
*l_out = lo;
*r_out = ro;
}
return 0;
}
static int
des_cipher(const u_char *in, u_char *out, u_int32_t salt, int count,
const struct _crypt_extended_shared *shared,
struct _crypt_extended_local *local)
{
u_int32_t l_out, r_out, rawl, rawr;
int retval;
setup_salt(salt, local);
rawl =
(u_int32_t)(u_char)in[3] |
((u_int32_t)(u_char)in[2] << 8) |
((u_int32_t)(u_char)in[1] << 16) |
((u_int32_t)(u_char)in[0] << 24);
rawr =
(u_int32_t)(u_char)in[7] |
((u_int32_t)(u_char)in[6] << 8) |
((u_int32_t)(u_char)in[5] << 16) |
((u_int32_t)(u_char)in[4] << 24);
retval = do_des(rawl, rawr, &l_out, &r_out, count, shared, local);
out[0] = l_out >> 24;
out[1] = l_out >> 16;
out[2] = l_out >> 8;
out[3] = l_out;
out[4] = r_out >> 24;
out[5] = r_out >> 16;
out[6] = r_out >> 8;
out[7] = r_out;
return retval;
}
char *
_crypt_extended_r(const char *key, const char *setting,
const struct _crypt_extended_shared *shared,
struct _crypt_extended_local *local)
{
int i;
u_int32_t count, salt, l, r0, r1, keybuf[2];
u_char *p, *q;
if (!local->initialized)
des_init_local(local);
/*
* Copy the key, shifting each character up by one bit
* and padding with zeros.
*/
q = (u_char *) keybuf;
while (q - (u_char *) keybuf < sizeof(keybuf)) {
*q++ = *key << 1;
if (*key)
key++;
}
if (des_setkey((u_char *) keybuf, shared, local))
return NULL;
if (*setting == _PASSWORD_EFMT1) {
/*
* "new"-style:
* setting - underscore, 4 chars of count, 4 chars of salt
* key - unlimited characters
*/
for (i = 1, count = 0; i < 5; i++) {
int value = ascii_to_bin(setting[i]);
if (ascii64[value] != setting[i])
return NULL;
count |= value << (i - 1) * 6;
}
if (!count)
return NULL;
for (i = 5, salt = 0; i < 9; i++) {
int value = ascii_to_bin(setting[i]);
if (ascii64[value] != setting[i])
return NULL;
salt |= value << (i - 5) * 6;
}
while (*key) {
/*
* Encrypt the key with itself.
*/
if (des_cipher((u_char *) keybuf, (u_char *) keybuf,
0, 1, shared, local))
return NULL;
/*
* And XOR with the next 8 characters of the key.
*/
q = (u_char *) keybuf;
while (q - (u_char *) keybuf < sizeof(keybuf) && *key)
*q++ ^= *key++ << 1;
if (des_setkey((u_char *) keybuf, shared, local))
return NULL;
}
memcpy(local->output, setting, 9);
local->output[9] = '\0';
p = (u_char *) local->output + 9;
} else {
/*
* "old"-style:
* setting - 2 chars of salt
* key - up to 8 characters
*/
count = 25;
if (ascii_is_unsafe(setting[0]) || ascii_is_unsafe(setting[1]))
return NULL;
salt = (ascii_to_bin(setting[1]) << 6)
| ascii_to_bin(setting[0]);
local->output[0] = setting[0];
local->output[1] = setting[1];
p = (u_char *) local->output + 2;
}
setup_salt(salt, local);
/*
* Do it.
*/
if (do_des(0, 0, &r0, &r1, count, shared, local))
return NULL;
/*
* Now encode the result...
*/
l = (r0 >> 8);
*p++ = ascii64[(l >> 18) & 0x3f];
*p++ = ascii64[(l >> 12) & 0x3f];
*p++ = ascii64[(l >> 6) & 0x3f];
*p++ = ascii64[l & 0x3f];
l = (r0 << 16) | ((r1 >> 16) & 0xffff);
*p++ = ascii64[(l >> 18) & 0x3f];
*p++ = ascii64[(l >> 12) & 0x3f];
*p++ = ascii64[(l >> 6) & 0x3f];
*p++ = ascii64[l & 0x3f];
l = r1 << 2;
*p++ = ascii64[(l >> 12) & 0x3f];
*p++ = ascii64[(l >> 6) & 0x3f];
*p++ = ascii64[l & 0x3f];
*p = 0;
return local->output;
}
#ifndef TEST_STATIC
#define TEST_STATIC /* not static */
#endif
#ifdef TEST
static char *
_crypt_extended(const char *key, const char *setting)
{
TEST_STATIC int initialized = 0;
TEST_STATIC struct _crypt_extended_shared shared;
/* "local" must be static since it holds our own return value */
static struct _crypt_extended_local local;
if (!initialized) {
memset(&shared, 's', sizeof(shared));
memset(&local, 'l', sizeof(local));
_crypt_extended_init(&shared);
initialized = 1;
local.initialized = 0;
}
return _crypt_extended_r(key, setting, &shared, &local);
}
static const struct {
char *hash;
char *pw;
} tests[] = {
/* "new"-style */
{"_J9..CCCCXBrJUJV154M", "U*U*U*U*"},
{"_J9..CCCCXUhOBTXzaiE", "U*U***U"},
{"_J9..CCCC4gQ.mB/PffM", "U*U***U*"},
{"_J9..XXXXvlzQGqpPPdk", "*U*U*U*U"},
{"_J9..XXXXsqM/YSSP..Y", "*U*U*U*U*"},
{"_J9..XXXXVL7qJCnku0I", "*U*U*U*U*U*U*U*U"},
{"_J9..XXXXAj8cFbP5scI", "*U*U*U*U*U*U*U*U*"},
{"_J9..SDizh.vll5VED9g", "ab1234567"},
{"_J9..SDizRjWQ/zePPHc", "cr1234567"},
{"_J9..SDizxmRI1GjnQuE", "zxyDPWgydbQjgq"},
{"_K9..SaltNrQgIYUAeoY", "726 even"},
{"_J9..SDSD5YGyRCr4W4c", ""},
{"_01234567IBjxKliXXRQ", "\xc3\x80" "1234abcd"},
{"_012345678OSGpGQRVHA", "\xc3\x80" "9234abcd"},
/* "old"-style, valid salts */
{"CCNf8Sbh3HDfQ", "U*U*U*U*"},
{"CCX.K.MFy4Ois", "U*U***U"},
{"CC4rMpbg9AMZ.", "U*U***U*"},
{"XXxzOu6maQKqQ", "*U*U*U*U"},
{"SDbsugeBiC58A", ""},
{"./xZjzHv5vzVE", "password"},
{"0A2hXM1rXbYgo", "password"},
{"A9RXdR23Y.cY6", "password"},
{"ZziFATVXHo2.6", "password"},
{"zZDDIZ0NOlPzw", "password"},
{"99PxawtsTfX56", "\xc3\x80" "1234abcd"},
{"99jcVcGxUZOWk", "\xc3\x80" "9234abcd"},
/* "old"-style, "reasonable" invalid salts, UFC-crypt behavior expected */
{"\001\002wyd0KZo65Jo", "password"},
{"a_C10Dk/ExaG.", "password"},
{"~\377.5OTsRVjwLo", "password"},
/* The below are erroneous inputs, so NULL return is expected/required */
{"", ""}, /* no salt */
{" ", ""}, /* setting string is too short */
{"a:", ""}, /* unsafe character */
{"\na", ""}, /* unsafe character */
{"_/......", ""}, /* setting string is too short for its type */
{"_........", ""}, /* zero iteration count */
{"_/!......", ""}, /* invalid character in count */
{"_/......!", ""}, /* invalid character in salt */
{NULL, NULL}
};
int main(void)
{
int i;
for (i = 0; tests[i].hash; i++) {
char *hash = _crypt_extended(tests[i].pw, tests[i].hash);
if (!hash && strlen(tests[i].hash) < 13)
continue; /* expected failure */
if (!strcmp(hash, tests[i].hash))
continue; /* expected success */
puts("FAILED");
return 1;
}
puts("PASSED");
return 0;
}
#endif
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: FreeSec crypt()
2012-06-12 23:51 FreeSec crypt() Solar Designer
@ 2012-06-13 1:18 ` Rich Felker
2012-06-13 6:10 ` Szabolcs Nagy
2012-06-13 12:07 ` Solar Designer
0 siblings, 2 replies; 17+ messages in thread
From: Rich Felker @ 2012-06-13 1:18 UTC (permalink / raw)
To: musl
[-- Attachment #1: Type: text/plain, Size: 1308 bytes --]
On Wed, Jun 13, 2012 at 03:51:13AM +0400, Solar Designer wrote:
> Rich -
>
> As discussed on IRC, here is a revision of the FreeSec crypt() code with
> greatly reduced memory requirements: 10 KB for the "shared" and "local"
> structs combined. The original code required about 70 KB of .bss.
Thanks. Here's a _really_ quick draft, untested, of the direction I
wanted to take it with making the tables static-initialized. Note that
doing so allowed removing all of the table-creation code and most of
the existing tables. For me, it's weighing in at ~12k. I also removed
some unused code for things like keeping salt/keys between multiple
runs since the data is not preserved across multiple runs anyway, and
the lookup tables for bitshifts.
> Also, we could want to add a runtime self-test, which would detect
> possible miscompiles.
I understand your motivation for doing this with security-critical
things, but really most/all of libc is security-critical, and we can't
have runtime miscompilation tests all over the place. Moreover, the
vast majority of cases of GCC "miscompiling" something turn out to be
code that's invoking undefined behavior; the only non-UB example I've
encountered while working on musl is gcc 4.7's bad breakage, which is
so bad you can't even get programs to start...
Rich
[-- Attachment #2: crypt.c --]
[-- Type: text/plain, Size: 41527 bytes --]
/*
* This version is derived from the original implementation of FreeSec
* (release 1.1) by David Burren. I've reviewed the changes made in
* OpenBSD (as of 2.7) and modified the original code in a similar way
* where applicable. I've also made it reentrant, reduced its memory
* usage (with only minimal performance impact), and made the handling
* of invalid salts mostly UFC-crypt compatible.
* - Solar Designer <solar at openwall.com>
*/
/*
* FreeSec: libcrypt for NetBSD
*
* Copyright (c) 1994 David Burren
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* 3. Neither the name of the author nor the names of other contributors
* may be used to endorse or promote products derived from this software
* without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*
* $Owl: Owl/packages/glibc/crypt_freesec.c,v 1.6 2010/02/20 14:45:06 solar Exp $
* $Id: crypt.c,v 1.15 1994/09/13 04:58:49 davidb Exp $
*
* This is an original implementation of the DES and the crypt(3) interfaces
* by David Burren <davidb at werj.com.au>.
*
* An excellent reference on the underlying algorithm (and related
* algorithms) is:
*
* B. Schneier, Applied Cryptography: protocols, algorithms,
* and source code in C, John Wiley & Sons, 1994.
*
* Note that in that book's description of DES the lookups for the initial,
* pbox, and final permutations are inverted (this has been brought to the
* attention of the author). A list of errata for this book has been
* posted to the sci.crypt newsgroup by the author and is available for FTP.
*
* ARCHITECTURE ASSUMPTIONS:
* This code used to have some nasty ones, but these have been removed
* by now. The code requires a 32-bit integer type, though.
*/
#include <sys/types.h>
#include <string.h>
struct _crypt_extended_local {
u_int32_t saltbits;
u_int32_t en_keysl[16], en_keysr[16];
};
#define _PASSWORD_EFMT1 '_'
static const u_char key_shifts[16] = {
1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1
};
static const uint32_t psbox[8][64] = {
{
0x00808200,0x00000000,0x00008000,0x00808202,
0x00808002,0x00008202,0x00000002,0x00008000,
0x00000200,0x00808200,0x00808202,0x00000200,
0x00800202,0x00808002,0x00800000,0x00000002,
0x00000202,0x00800200,0x00800200,0x00008200,
0x00008200,0x00808000,0x00808000,0x00800202,
0x00008002,0x00800002,0x00800002,0x00008002,
0x00000000,0x00000202,0x00008202,0x00800000,
0x00008000,0x00808202,0x00000002,0x00808000,
0x00808200,0x00800000,0x00800000,0x00000200,
0x00808002,0x00008000,0x00008200,0x00800002,
0x00000200,0x00000002,0x00800202,0x00008202,
0x00808202,0x00008002,0x00808000,0x00800202,
0x00800002,0x00000202,0x00008202,0x00808200,
0x00000202,0x00800200,0x00800200,0x00000000,
0x00008002,0x00008200,0x00000000,0x00808002,
},{
0x40084010,0x40004000,0x00004000,0x00084010,
0x00080000,0x00000010,0x40080010,0x40004010,
0x40000010,0x40084010,0x40084000,0x40000000,
0x40004000,0x00080000,0x00000010,0x40080010,
0x00084000,0x00080010,0x40004010,0x00000000,
0x40000000,0x00004000,0x00084010,0x40080000,
0x00080010,0x40000010,0x00000000,0x00084000,
0x00004010,0x40084000,0x40080000,0x00004010,
0x00000000,0x00084010,0x40080010,0x00080000,
0x40004010,0x40080000,0x40084000,0x00004000,
0x40080000,0x40004000,0x00000010,0x40084010,
0x00084010,0x00000010,0x00004000,0x40000000,
0x00004010,0x40084000,0x00080000,0x40000010,
0x00080010,0x40004010,0x40000010,0x00080010,
0x00084000,0x00000000,0x40004000,0x00004010,
0x40000000,0x40080010,0x40084010,0x00084000,
},{
0x00000104,0x04010100,0x00000000,0x04010004,
0x04000100,0x00000000,0x00010104,0x04000100,
0x00010004,0x04000004,0x04000004,0x00010000,
0x04010104,0x00010004,0x04010000,0x00000104,
0x04000000,0x00000004,0x04010100,0x00000100,
0x00010100,0x04010000,0x04010004,0x00010104,
0x04000104,0x00010100,0x00010000,0x04000104,
0x00000004,0x04010104,0x00000100,0x04000000,
0x04010100,0x04000000,0x00010004,0x00000104,
0x00010000,0x04010100,0x04000100,0x00000000,
0x00000100,0x00010004,0x04010104,0x04000100,
0x04000004,0x00000100,0x00000000,0x04010004,
0x04000104,0x00010000,0x04000000,0x04010104,
0x00000004,0x00010104,0x00010100,0x04000004,
0x04010000,0x04000104,0x00000104,0x04010000,
0x00010104,0x00000004,0x04010004,0x00010100,
},{
0x80401000,0x80001040,0x80001040,0x00000040,
0x00401040,0x80400040,0x80400000,0x80001000,
0x00000000,0x00401000,0x00401000,0x80401040,
0x80000040,0x00000000,0x00400040,0x80400000,
0x80000000,0x00001000,0x00400000,0x80401000,
0x00000040,0x00400000,0x80001000,0x00001040,
0x80400040,0x80000000,0x00001040,0x00400040,
0x00001000,0x00401040,0x80401040,0x80000040,
0x00400040,0x80400000,0x00401000,0x80401040,
0x80000040,0x00000000,0x00000000,0x00401000,
0x00001040,0x00400040,0x80400040,0x80000000,
0x80401000,0x80001040,0x80001040,0x00000040,
0x80401040,0x80000040,0x80000000,0x00001000,
0x80400000,0x80001000,0x00401040,0x80400040,
0x80001000,0x00001040,0x00400000,0x80401000,
0x00000040,0x00400000,0x00001000,0x00401040,
},{
0x00000080,0x01040080,0x01040000,0x21000080,
0x00040000,0x00000080,0x20000000,0x01040000,
0x20040080,0x00040000,0x01000080,0x20040080,
0x21000080,0x21040000,0x00040080,0x20000000,
0x01000000,0x20040000,0x20040000,0x00000000,
0x20000080,0x21040080,0x21040080,0x01000080,
0x21040000,0x20000080,0x00000000,0x21000000,
0x01040080,0x01000000,0x21000000,0x00040080,
0x00040000,0x21000080,0x00000080,0x01000000,
0x20000000,0x01040000,0x21000080,0x20040080,
0x01000080,0x20000000,0x21040000,0x01040080,
0x20040080,0x00000080,0x01000000,0x21040000,
0x21040080,0x00040080,0x21000000,0x21040080,
0x01040000,0x00000000,0x20040000,0x21000000,
0x00040080,0x01000080,0x20000080,0x00040000,
0x00000000,0x20040000,0x01040080,0x20000080,
},{
0x10000008,0x10200000,0x00002000,0x10202008,
0x10200000,0x00000008,0x10202008,0x00200000,
0x10002000,0x00202008,0x00200000,0x10000008,
0x00200008,0x10002000,0x10000000,0x00002008,
0x00000000,0x00200008,0x10002008,0x00002000,
0x00202000,0x10002008,0x00000008,0x10200008,
0x10200008,0x00000000,0x00202008,0x10202000,
0x00002008,0x00202000,0x10202000,0x10000000,
0x10002000,0x00000008,0x10200008,0x00202000,
0x10202008,0x00200000,0x00002008,0x10000008,
0x00200000,0x10002000,0x10000000,0x00002008,
0x10000008,0x10202008,0x00202000,0x10200000,
0x00202008,0x10202000,0x00000000,0x10200008,
0x00000008,0x00002000,0x10200000,0x00202008,
0x00002000,0x00200008,0x10002008,0x00000000,
0x10202000,0x10000000,0x00200008,0x10002008,
},{
0x00100000,0x02100001,0x02000401,0x00000000,
0x00000400,0x02000401,0x00100401,0x02100400,
0x02100401,0x00100000,0x00000000,0x02000001,
0x00000001,0x02000000,0x02100001,0x00000401,
0x02000400,0x00100401,0x00100001,0x02000400,
0x02000001,0x02100000,0x02100400,0x00100001,
0x02100000,0x00000400,0x00000401,0x02100401,
0x00100400,0x00000001,0x02000000,0x00100400,
0x02000000,0x00100400,0x00100000,0x02000401,
0x02000401,0x02100001,0x02100001,0x00000001,
0x00100001,0x02000000,0x02000400,0x00100000,
0x02100400,0x00000401,0x00100401,0x02100400,
0x00000401,0x02000001,0x02100401,0x02100000,
0x00100400,0x00000000,0x00000001,0x02100401,
0x00000000,0x00100401,0x02100000,0x00000400,
0x02000001,0x02000400,0x00000400,0x00100001,
},{
0x08000820,0x00000800,0x00020000,0x08020820,
0x08000000,0x08000820,0x00000020,0x08000000,
0x00020020,0x08020000,0x08020820,0x00020800,
0x08020800,0x00020820,0x00000800,0x00000020,
0x08020000,0x08000020,0x08000800,0x00000820,
0x00020800,0x00020020,0x08020020,0x08020800,
0x00000820,0x00000000,0x00000000,0x08020020,
0x08000020,0x08000800,0x00020820,0x00020000,
0x00020820,0x00020000,0x08020800,0x00000800,
0x00000020,0x08020020,0x00000800,0x00020820,
0x08000800,0x00000020,0x08000020,0x08020000,
0x08020020,0x08000000,0x00020000,0x08000820,
0x00000000,0x08020820,0x00020020,0x08000020,
0x08020000,0x08000800,0x08000820,0x00000000,
0x08020820,0x00020800,0x00020800,0x00000820,
0x00000820,0x00020020,0x08000000,0x08020800,
},
};
static const uint32_t ip_maskl[16][16] = {
{
0x00000000,0x00010000,0x00000000,0x00010000,
0x01000000,0x01010000,0x01000000,0x01010000,
0x00000000,0x00010000,0x00000000,0x00010000,
0x01000000,0x01010000,0x01000000,0x01010000,
},{
0x00000000,0x00000001,0x00000000,0x00000001,
0x00000100,0x00000101,0x00000100,0x00000101,
0x00000000,0x00000001,0x00000000,0x00000001,
0x00000100,0x00000101,0x00000100,0x00000101,
},{
0x00000000,0x00020000,0x00000000,0x00020000,
0x02000000,0x02020000,0x02000000,0x02020000,
0x00000000,0x00020000,0x00000000,0x00020000,
0x02000000,0x02020000,0x02000000,0x02020000,
},{
0x00000000,0x00000002,0x00000000,0x00000002,
0x00000200,0x00000202,0x00000200,0x00000202,
0x00000000,0x00000002,0x00000000,0x00000002,
0x00000200,0x00000202,0x00000200,0x00000202,
},{
0x00000000,0x00040000,0x00000000,0x00040000,
0x04000000,0x04040000,0x04000000,0x04040000,
0x00000000,0x00040000,0x00000000,0x00040000,
0x04000000,0x04040000,0x04000000,0x04040000,
},{
0x00000000,0x00000004,0x00000000,0x00000004,
0x00000400,0x00000404,0x00000400,0x00000404,
0x00000000,0x00000004,0x00000000,0x00000004,
0x00000400,0x00000404,0x00000400,0x00000404,
},{
0x00000000,0x00080000,0x00000000,0x00080000,
0x08000000,0x08080000,0x08000000,0x08080000,
0x00000000,0x00080000,0x00000000,0x00080000,
0x08000000,0x08080000,0x08000000,0x08080000,
},{
0x00000000,0x00000008,0x00000000,0x00000008,
0x00000800,0x00000808,0x00000800,0x00000808,
0x00000000,0x00000008,0x00000000,0x00000008,
0x00000800,0x00000808,0x00000800,0x00000808,
},{
0x00000000,0x00100000,0x00000000,0x00100000,
0x10000000,0x10100000,0x10000000,0x10100000,
0x00000000,0x00100000,0x00000000,0x00100000,
0x10000000,0x10100000,0x10000000,0x10100000,
},{
0x00000000,0x00000010,0x00000000,0x00000010,
0x00001000,0x00001010,0x00001000,0x00001010,
0x00000000,0x00000010,0x00000000,0x00000010,
0x00001000,0x00001010,0x00001000,0x00001010,
},{
0x00000000,0x00200000,0x00000000,0x00200000,
0x20000000,0x20200000,0x20000000,0x20200000,
0x00000000,0x00200000,0x00000000,0x00200000,
0x20000000,0x20200000,0x20000000,0x20200000,
},{
0x00000000,0x00000020,0x00000000,0x00000020,
0x00002000,0x00002020,0x00002000,0x00002020,
0x00000000,0x00000020,0x00000000,0x00000020,
0x00002000,0x00002020,0x00002000,0x00002020,
},{
0x00000000,0x00400000,0x00000000,0x00400000,
0x40000000,0x40400000,0x40000000,0x40400000,
0x00000000,0x00400000,0x00000000,0x00400000,
0x40000000,0x40400000,0x40000000,0x40400000,
},{
0x00000000,0x00000040,0x00000000,0x00000040,
0x00004000,0x00004040,0x00004000,0x00004040,
0x00000000,0x00000040,0x00000000,0x00000040,
0x00004000,0x00004040,0x00004000,0x00004040,
},{
0x00000000,0x00800000,0x00000000,0x00800000,
0x80000000,0x80800000,0x80000000,0x80800000,
0x00000000,0x00800000,0x00000000,0x00800000,
0x80000000,0x80800000,0x80000000,0x80800000,
},{
0x00000000,0x00000080,0x00000000,0x00000080,
0x00008000,0x00008080,0x00008000,0x00008080,
0x00000000,0x00000080,0x00000000,0x00000080,
0x00008000,0x00008080,0x00008000,0x00008080,
},
};
static const uint32_t ip_maskr[16][16] = {
{
0x00000000,0x00000000,0x00010000,0x00010000,
0x00000000,0x00000000,0x00010000,0x00010000,
0x01000000,0x01000000,0x01010000,0x01010000,
0x01000000,0x01000000,0x01010000,0x01010000,
},{
0x00000000,0x00000000,0x00000001,0x00000001,
0x00000000,0x00000000,0x00000001,0x00000001,
0x00000100,0x00000100,0x00000101,0x00000101,
0x00000100,0x00000100,0x00000101,0x00000101,
},{
0x00000000,0x00000000,0x00020000,0x00020000,
0x00000000,0x00000000,0x00020000,0x00020000,
0x02000000,0x02000000,0x02020000,0x02020000,
0x02000000,0x02000000,0x02020000,0x02020000,
},{
0x00000000,0x00000000,0x00000002,0x00000002,
0x00000000,0x00000000,0x00000002,0x00000002,
0x00000200,0x00000200,0x00000202,0x00000202,
0x00000200,0x00000200,0x00000202,0x00000202,
},{
0x00000000,0x00000000,0x00040000,0x00040000,
0x00000000,0x00000000,0x00040000,0x00040000,
0x04000000,0x04000000,0x04040000,0x04040000,
0x04000000,0x04000000,0x04040000,0x04040000,
},{
0x00000000,0x00000000,0x00000004,0x00000004,
0x00000000,0x00000000,0x00000004,0x00000004,
0x00000400,0x00000400,0x00000404,0x00000404,
0x00000400,0x00000400,0x00000404,0x00000404,
},{
0x00000000,0x00000000,0x00080000,0x00080000,
0x00000000,0x00000000,0x00080000,0x00080000,
0x08000000,0x08000000,0x08080000,0x08080000,
0x08000000,0x08000000,0x08080000,0x08080000,
},{
0x00000000,0x00000000,0x00000008,0x00000008,
0x00000000,0x00000000,0x00000008,0x00000008,
0x00000800,0x00000800,0x00000808,0x00000808,
0x00000800,0x00000800,0x00000808,0x00000808,
},{
0x00000000,0x00000000,0x00100000,0x00100000,
0x00000000,0x00000000,0x00100000,0x00100000,
0x10000000,0x10000000,0x10100000,0x10100000,
0x10000000,0x10000000,0x10100000,0x10100000,
},{
0x00000000,0x00000000,0x00000010,0x00000010,
0x00000000,0x00000000,0x00000010,0x00000010,
0x00001000,0x00001000,0x00001010,0x00001010,
0x00001000,0x00001000,0x00001010,0x00001010,
},{
0x00000000,0x00000000,0x00200000,0x00200000,
0x00000000,0x00000000,0x00200000,0x00200000,
0x20000000,0x20000000,0x20200000,0x20200000,
0x20000000,0x20000000,0x20200000,0x20200000,
},{
0x00000000,0x00000000,0x00000020,0x00000020,
0x00000000,0x00000000,0x00000020,0x00000020,
0x00002000,0x00002000,0x00002020,0x00002020,
0x00002000,0x00002000,0x00002020,0x00002020,
},{
0x00000000,0x00000000,0x00400000,0x00400000,
0x00000000,0x00000000,0x00400000,0x00400000,
0x40000000,0x40000000,0x40400000,0x40400000,
0x40000000,0x40000000,0x40400000,0x40400000,
},{
0x00000000,0x00000000,0x00000040,0x00000040,
0x00000000,0x00000000,0x00000040,0x00000040,
0x00004000,0x00004000,0x00004040,0x00004040,
0x00004000,0x00004000,0x00004040,0x00004040,
},{
0x00000000,0x00000000,0x00800000,0x00800000,
0x00000000,0x00000000,0x00800000,0x00800000,
0x80000000,0x80000000,0x80800000,0x80800000,
0x80000000,0x80000000,0x80800000,0x80800000,
},{
0x00000000,0x00000000,0x00000080,0x00000080,
0x00000000,0x00000000,0x00000080,0x00000080,
0x00008000,0x00008000,0x00008080,0x00008080,
0x00008000,0x00008000,0x00008080,0x00008080,
},
};
static const uint32_t fp_maskl[16][16] = {
{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x40000000,0x00400000,0x40400000,
0x00004000,0x40004000,0x00404000,0x40404000,
0x00000040,0x40000040,0x00400040,0x40400040,
0x00004040,0x40004040,0x00404040,0x40404040,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x10000000,0x00100000,0x10100000,
0x00001000,0x10001000,0x00101000,0x10101000,
0x00000010,0x10000010,0x00100010,0x10100010,
0x00001010,0x10001010,0x00101010,0x10101010,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x04000000,0x00040000,0x04040000,
0x00000400,0x04000400,0x00040400,0x04040400,
0x00000004,0x04000004,0x00040004,0x04040004,
0x00000404,0x04000404,0x00040404,0x04040404,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x01000000,0x00010000,0x01010000,
0x00000100,0x01000100,0x00010100,0x01010100,
0x00000001,0x01000001,0x00010001,0x01010001,
0x00000101,0x01000101,0x00010101,0x01010101,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x80000000,0x00800000,0x80800000,
0x00008000,0x80008000,0x00808000,0x80808000,
0x00000080,0x80000080,0x00800080,0x80800080,
0x00008080,0x80008080,0x00808080,0x80808080,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x20000000,0x00200000,0x20200000,
0x00002000,0x20002000,0x00202000,0x20202000,
0x00000020,0x20000020,0x00200020,0x20200020,
0x00002020,0x20002020,0x00202020,0x20202020,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x08000000,0x00080000,0x08080000,
0x00000800,0x08000800,0x00080800,0x08080800,
0x00000008,0x08000008,0x00080008,0x08080008,
0x00000808,0x08000808,0x00080808,0x08080808,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x02000000,0x00020000,0x02020000,
0x00000200,0x02000200,0x00020200,0x02020200,
0x00000002,0x02000002,0x00020002,0x02020002,
0x00000202,0x02000202,0x00020202,0x02020202,
},
};
static const uint32_t fp_maskr[16][16] = {
{
0x00000000,0x40000000,0x00400000,0x40400000,
0x00004000,0x40004000,0x00404000,0x40404000,
0x00000040,0x40000040,0x00400040,0x40400040,
0x00004040,0x40004040,0x00404040,0x40404040,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x10000000,0x00100000,0x10100000,
0x00001000,0x10001000,0x00101000,0x10101000,
0x00000010,0x10000010,0x00100010,0x10100010,
0x00001010,0x10001010,0x00101010,0x10101010,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x04000000,0x00040000,0x04040000,
0x00000400,0x04000400,0x00040400,0x04040400,
0x00000004,0x04000004,0x00040004,0x04040004,
0x00000404,0x04000404,0x00040404,0x04040404,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x01000000,0x00010000,0x01010000,
0x00000100,0x01000100,0x00010100,0x01010100,
0x00000001,0x01000001,0x00010001,0x01010001,
0x00000101,0x01000101,0x00010101,0x01010101,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x80000000,0x00800000,0x80800000,
0x00008000,0x80008000,0x00808000,0x80808000,
0x00000080,0x80000080,0x00800080,0x80800080,
0x00008080,0x80008080,0x00808080,0x80808080,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x20000000,0x00200000,0x20200000,
0x00002000,0x20002000,0x00202000,0x20202000,
0x00000020,0x20000020,0x00200020,0x20200020,
0x00002020,0x20002020,0x00202020,0x20202020,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x08000000,0x00080000,0x08080000,
0x00000800,0x08000800,0x00080800,0x08080800,
0x00000008,0x08000008,0x00080008,0x08080008,
0x00000808,0x08000808,0x00080808,0x08080808,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x02000000,0x00020000,0x02020000,
0x00000200,0x02000200,0x00020200,0x02020200,
0x00000002,0x02000002,0x00020002,0x02020002,
0x00000202,0x02000202,0x00020202,0x02020202,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},
};
static const uint32_t key_perm_maskl[16][16] = {
{
0x00000000,0x00000000,0x00000010,0x00000010,
0x00001000,0x00001000,0x00001010,0x00001010,
0x00100000,0x00100000,0x00100010,0x00100010,
0x00101000,0x00101000,0x00101010,0x00101010,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x00000000,0x00000020,0x00000020,
0x00002000,0x00002000,0x00002020,0x00002020,
0x00200000,0x00200000,0x00200020,0x00200020,
0x00202000,0x00202000,0x00202020,0x00202020,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x00000000,0x00000040,0x00000040,
0x00004000,0x00004000,0x00004040,0x00004040,
0x00400000,0x00400000,0x00400040,0x00400040,
0x00404000,0x00404000,0x00404040,0x00404040,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x00000000,0x00000080,0x00000080,
0x00008000,0x00008000,0x00008080,0x00008080,
0x00800000,0x00800000,0x00800080,0x00800080,
0x00808000,0x00808000,0x00808080,0x00808080,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x00000001,0x00000100,0x00000101,
0x00010000,0x00010001,0x00010100,0x00010101,
0x01000000,0x01000001,0x01000100,0x01000101,
0x01010000,0x01010001,0x01010100,0x01010101,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x00000002,0x00000200,0x00000202,
0x00020000,0x00020002,0x00020200,0x00020202,
0x02000000,0x02000002,0x02000200,0x02000202,
0x02020000,0x02020002,0x02020200,0x02020202,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x00000004,0x00000400,0x00000404,
0x00040000,0x00040004,0x00040400,0x00040404,
0x04000000,0x04000004,0x04000400,0x04000404,
0x04040000,0x04040004,0x04040400,0x04040404,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x00000008,0x00000800,0x00000808,
0x00080000,0x00080008,0x00080800,0x00080808,
0x08000000,0x08000008,0x08000800,0x08000808,
0x08080000,0x08080008,0x08080800,0x08080808,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},
};
static const uint32_t key_perm_maskr[16][16] = {
{
0x00000000,0x00000001,0x00000000,0x00000001,
0x00000000,0x00000001,0x00000000,0x00000001,
0x00000000,0x00000001,0x00000000,0x00000001,
0x00000000,0x00000001,0x00000000,0x00000001,
},{
0x00000000,0x00000000,0x00100000,0x00100000,
0x00001000,0x00001000,0x00101000,0x00101000,
0x00000010,0x00000010,0x00100010,0x00100010,
0x00001010,0x00001010,0x00101010,0x00101010,
},{
0x00000000,0x00000002,0x00000000,0x00000002,
0x00000000,0x00000002,0x00000000,0x00000002,
0x00000000,0x00000002,0x00000000,0x00000002,
0x00000000,0x00000002,0x00000000,0x00000002,
},{
0x00000000,0x00000000,0x00200000,0x00200000,
0x00002000,0x00002000,0x00202000,0x00202000,
0x00000020,0x00000020,0x00200020,0x00200020,
0x00002020,0x00002020,0x00202020,0x00202020,
},{
0x00000000,0x00000004,0x00000000,0x00000004,
0x00000000,0x00000004,0x00000000,0x00000004,
0x00000000,0x00000004,0x00000000,0x00000004,
0x00000000,0x00000004,0x00000000,0x00000004,
},{
0x00000000,0x00000000,0x00400000,0x00400000,
0x00004000,0x00004000,0x00404000,0x00404000,
0x00000040,0x00000040,0x00400040,0x00400040,
0x00004040,0x00004040,0x00404040,0x00404040,
},{
0x00000000,0x00000008,0x00000000,0x00000008,
0x00000000,0x00000008,0x00000000,0x00000008,
0x00000000,0x00000008,0x00000000,0x00000008,
0x00000000,0x00000008,0x00000000,0x00000008,
},{
0x00000000,0x00000000,0x00800000,0x00800000,
0x00008000,0x00008000,0x00808000,0x00808000,
0x00000080,0x00000080,0x00800080,0x00800080,
0x00008080,0x00008080,0x00808080,0x00808080,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x00000000,0x01000000,0x01000000,
0x00010000,0x00010000,0x01010000,0x01010000,
0x00000100,0x00000100,0x01000100,0x01000100,
0x00010100,0x00010100,0x01010100,0x01010100,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x00000000,0x02000000,0x02000000,
0x00020000,0x00020000,0x02020000,0x02020000,
0x00000200,0x00000200,0x02000200,0x02000200,
0x00020200,0x00020200,0x02020200,0x02020200,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x00000000,0x04000000,0x04000000,
0x00040000,0x00040000,0x04040000,0x04040000,
0x00000400,0x00000400,0x04000400,0x04000400,
0x00040400,0x00040400,0x04040400,0x04040400,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x00000000,0x08000000,0x08000000,
0x00080000,0x00080000,0x08080000,0x08080000,
0x00000800,0x00000800,0x08000800,0x08000800,
0x00080800,0x00080800,0x08080800,0x08080800,
},
};
static const uint32_t comp_maskl0[8][8] = {
{
0x00000000,0x00020000,0x00000001,0x00020001,
0x00080000,0x000a0000,0x00080001,0x000a0001,
},{
0x00000000,0x00001000,0x00000000,0x00001000,
0x00000040,0x00001040,0x00000040,0x00001040,
},{
0x00000000,0x00400000,0x00000020,0x00400020,
0x00008000,0x00408000,0x00008020,0x00408020,
},{
0x00000000,0x00100000,0x00000800,0x00100800,
0x00000000,0x00100000,0x00000800,0x00100800,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},
};
static const uint32_t comp_maskr0[8][8] = {
{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x00200000,0x00020000,0x00220000,
0x00000002,0x00200002,0x00020002,0x00220002,
},{
0x00000000,0x00000000,0x00100000,0x00100000,
0x00000004,0x00000004,0x00100004,0x00100004,
},{
0x00000000,0x00004000,0x00000800,0x00004800,
0x00000000,0x00004000,0x00000800,0x00004800,
},{
0x00000000,0x00400000,0x00008000,0x00408000,
0x00000008,0x00400008,0x00008008,0x00408008,
},
};
static const uint32_t comp_maskl1[8][16] = {
{
0x00000000,0x00000010,0x00004000,0x00004010,
0x00040000,0x00040010,0x00044000,0x00044010,
0x00000100,0x00000110,0x00004100,0x00004110,
0x00040100,0x00040110,0x00044100,0x00044110,
},{
0x00000000,0x00800000,0x00000002,0x00800002,
0x00000200,0x00800200,0x00000202,0x00800202,
0x00200000,0x00a00000,0x00200002,0x00a00002,
0x00200200,0x00a00200,0x00200202,0x00a00202,
},{
0x00000000,0x00002000,0x00000004,0x00002004,
0x00000400,0x00002400,0x00000404,0x00002404,
0x00000000,0x00002000,0x00000004,0x00002004,
0x00000400,0x00002400,0x00000404,0x00002404,
},{
0x00000000,0x00010000,0x00000008,0x00010008,
0x00000080,0x00010080,0x00000088,0x00010088,
0x00000000,0x00010000,0x00000008,0x00010008,
0x00000080,0x00010080,0x00000088,0x00010088,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},
};
static const uint32_t comp_maskr1[8][16] = {
{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
0x00000000,0x00000000,0x00000000,0x00000000,
},{
0x00000000,0x00000000,0x00000080,0x00000080,
0x00002000,0x00002000,0x00002080,0x00002080,
0x00000001,0x00000001,0x00000081,0x00000081,
0x00002001,0x00002001,0x00002081,0x00002081,
},{
0x00000000,0x00000010,0x00800000,0x00800010,
0x00010000,0x00010010,0x00810000,0x00810010,
0x00000200,0x00000210,0x00800200,0x00800210,
0x00010200,0x00010210,0x00810200,0x00810210,
},{
0x00000000,0x00000400,0x00001000,0x00001400,
0x00080000,0x00080400,0x00081000,0x00081400,
0x00000020,0x00000420,0x00001020,0x00001420,
0x00080020,0x00080420,0x00081020,0x00081420,
},{
0x00000000,0x00000100,0x00040000,0x00040100,
0x00000000,0x00000100,0x00040000,0x00040100,
0x00000040,0x00000140,0x00040040,0x00040140,
0x00000040,0x00000140,0x00040040,0x00040140,
},
};
static const u_char ascii64[] =
"./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
/* 0000000000111111111122222222223333333333444444444455555555556666 */
/* 0123456789012345678901234567890123456789012345678901234567890123 */
/*
* We match the behavior of UFC-crypt on systems where "char" is signed by
* default (the majority), regardless of char's signedness on our system.
*/
static inline int
ascii_to_bin(int ch)
{
int sch = ch>127 ? -(256-ch) : ch;
int retval;
retval = sch - '.';
if (sch >= 'A') {
retval = sch - ('A' - 12);
if (sch >= 'a')
retval = sch - ('a' - 38);
}
retval &= 0x3f;
return retval;
}
/*
* When we choose to "support" invalid salts, nevertheless disallow those
* containing characters that would violate the passwd file format.
*/
static inline int
ascii_is_unsafe(int ch)
{
return !ch || ch == '\n' || ch == ':';
}
static void
setup_salt(u_int32_t salt, struct _crypt_extended_local *local)
{
u_int32_t obit, saltbit, saltbits;
int i;
saltbits = 0;
saltbit = 1;
obit = 0x800000;
for (i = 0; i < 24; i++) {
if (salt & saltbit)
saltbits |= obit;
saltbit <<= 1;
obit >>= 1;
}
local->saltbits = saltbits;
}
static int
des_setkey(const u_char *key,
struct _crypt_extended_local *local)
{
u_int32_t k0, k1, rawkey0, rawkey1;
int shifts, round;
rawkey0 =
(u_int32_t)(u_char)key[3] |
((u_int32_t)(u_char)key[2] << 8) |
((u_int32_t)(u_char)key[1] << 16) |
((u_int32_t)(u_char)key[0] << 24);
rawkey1 =
(u_int32_t)(u_char)key[7] |
((u_int32_t)(u_char)key[6] << 8) |
((u_int32_t)(u_char)key[5] << 16) |
((u_int32_t)(u_char)key[4] << 24);
/*
* Do key permutation and split into two 28-bit subkeys.
*/
{
int i, inbit;
k0 = k1 = 0;
for (i = 0, inbit = 28; i < 8; i++, inbit -= 4) {
k0 |= key_perm_maskl[i][(rawkey0 >> inbit) & 0xf] |
key_perm_maskl[i + 8][(rawkey1 >> inbit) & 0xf];
k1 |= key_perm_maskr[i][(rawkey0 >> inbit) & 0xf] |
key_perm_maskr[i + 8][(rawkey1 >> inbit) & 0xf];
}
}
/*
* Rotate subkeys and do compression permutation.
*/
shifts = 0;
for (round = 0; round < 16; round++) {
u_int32_t t0, t1;
shifts += key_shifts[round];
t0 = (k0 << shifts) | (k0 >> (28 - shifts));
t1 = (k1 << shifts) | (k1 >> (28 - shifts));
{
int i, inbit;
u_int32_t kl, kr;
kl = kr = 0;
inbit = 25;
for (i = 0; i < 4; i++) {
kl |= comp_maskl0[i][(t0 >> inbit) & 7] |
comp_maskl0[i + 4][(t1 >> inbit) & 7];
kr |= comp_maskr0[i][(t0 >> inbit) & 7] |
comp_maskr0[i + 4][(t1 >> inbit) & 7];
inbit -= 4;
kl |= comp_maskl1[i][(t0 >> inbit) & 0xf] |
comp_maskl1[i + 4][(t1 >> inbit) & 0xf];
kr |= comp_maskr1[i][(t0 >> inbit) & 0xf] |
comp_maskr1[i + 4][(t1 >> inbit) & 0xf];
inbit -= 3;
}
local->en_keysl[round] = kl;
local->en_keysr[round] = kr;
}
}
return 0;
}
static int
do_des(u_int32_t l_in, u_int32_t r_in, u_int32_t *l_out, u_int32_t *r_out,
int count,
struct _crypt_extended_local *local)
{
/*
* l_in, r_in, l_out, and r_out are in pseudo-"big-endian" format.
*/
u_int32_t l, r, *kl, *kr, *kl1, *kr1;
u_int32_t f, r48l, r48r, saltbits;
int round;
kl1 = local->en_keysl;
kr1 = local->en_keysr;
/*
* Do initial permutation (IP).
*/
l = r = 0;
if (l_in | r_in) {
int i, inbit;
for (i = 0, inbit = 28; i < 8; i++, inbit -= 4) {
l |= ip_maskl[i][(l_in >> inbit) & 0xf] |
ip_maskl[i + 8][(r_in >> inbit) & 0xf];
r |= ip_maskr[i][(l_in >> inbit) & 0xf] |
ip_maskr[i + 8][(r_in >> inbit) & 0xf];
}
}
saltbits = local->saltbits;
while (count--) {
/*
* Do each round.
*/
kl = kl1;
kr = kr1;
round = 16;
while (round--) {
/*
* Expand R to 48 bits (simulate the E-box).
*/
r48l = ((r & 0x00000001) << 23)
| ((r & 0xf8000000) >> 9)
| ((r & 0x1f800000) >> 11)
| ((r & 0x01f80000) >> 13)
| ((r & 0x001f8000) >> 15);
r48r = ((r & 0x0001f800) << 7)
| ((r & 0x00001f80) << 5)
| ((r & 0x000001f8) << 3)
| ((r & 0x0000001f) << 1)
| ((r & 0x80000000) >> 31);
/*
* Do salting for crypt() and friends, and
* XOR with the permuted key.
*/
f = (r48l ^ r48r) & saltbits;
r48l ^= f ^ *kl++;
r48r ^= f ^ *kr++;
/*
* Do S-box lookups (which shrink it back to 32 bits)
* and do the P-box permutation at the same time.
*/
f = psbox[0][r48l >> 18]
| psbox[1][(r48l >> 12) & 0x3f]
| psbox[2][(r48l >> 6) & 0x3f]
| psbox[3][r48l & 0x3f]
| psbox[4][r48r >> 18]
| psbox[5][(r48r >> 12) & 0x3f]
| psbox[6][(r48r >> 6) & 0x3f]
| psbox[7][r48r & 0x3f];
/*
* Now that we've permuted things, complete f().
*/
f ^= l;
l = r;
r = f;
}
r = l;
l = f;
}
/*
* Do final permutation (inverse of IP).
*/
{
int i, inbit;
u_int32_t lo, ro;
lo = ro = 0;
for (i = 0, inbit = 28; i < 8; i++, inbit -= 4) {
lo |= fp_maskl[i][(l >> inbit) & 0xf] |
fp_maskl[i + 8][(r >> inbit) & 0xf];
ro |= fp_maskr[i][(l >> inbit) & 0xf] |
fp_maskr[i + 8][(r >> inbit) & 0xf];
}
*l_out = lo;
*r_out = ro;
}
return 0;
}
static int
des_cipher(const u_char *in, u_char *out, u_int32_t salt, int count,
struct _crypt_extended_local *local)
{
u_int32_t l_out, r_out, rawl, rawr;
int retval;
setup_salt(salt, local);
rawl =
(u_int32_t)(u_char)in[3] |
((u_int32_t)(u_char)in[2] << 8) |
((u_int32_t)(u_char)in[1] << 16) |
((u_int32_t)(u_char)in[0] << 24);
rawr =
(u_int32_t)(u_char)in[7] |
((u_int32_t)(u_char)in[6] << 8) |
((u_int32_t)(u_char)in[5] << 16) |
((u_int32_t)(u_char)in[4] << 24);
retval = do_des(rawl, rawr, &l_out, &r_out, count, local);
out[0] = l_out >> 24;
out[1] = l_out >> 16;
out[2] = l_out >> 8;
out[3] = l_out;
out[4] = r_out >> 24;
out[5] = r_out >> 16;
out[6] = r_out >> 8;
out[7] = r_out;
return retval;
}
char *
_crypt_extended_r(const char *key, const char *setting, char *output)
{
int i;
u_int32_t count, salt, l, r0, r1, keybuf[2];
u_char *p, *q;
struct _crypt_extended_local local = { 0 };
/*
* Copy the key, shifting each character up by one bit
* and padding with zeros.
*/
q = (u_char *) keybuf;
while (q - (u_char *) keybuf < sizeof(keybuf)) {
*q++ = *key << 1;
if (*key)
key++;
}
if (des_setkey((u_char *) keybuf, &local))
return NULL;
if (*setting == _PASSWORD_EFMT1) {
/*
* "new"-style:
* setting - underscore, 4 chars of count, 4 chars of salt
* key - unlimited characters
*/
for (i = 1, count = 0; i < 5; i++) {
int value = ascii_to_bin(setting[i]);
if (ascii64[value] != setting[i])
return NULL;
count |= value << (i - 1) * 6;
}
if (!count)
return NULL;
for (i = 5, salt = 0; i < 9; i++) {
int value = ascii_to_bin(setting[i]);
if (ascii64[value] != setting[i])
return NULL;
salt |= value << (i - 5) * 6;
}
while (*key) {
/*
* Encrypt the key with itself.
*/
if (des_cipher((u_char *) keybuf, (u_char *) keybuf,
0, 1, &local))
return NULL;
/*
* And XOR with the next 8 characters of the key.
*/
q = (u_char *) keybuf;
while (q - (u_char *) keybuf < sizeof(keybuf) && *key)
*q++ ^= *key++ << 1;
if (des_setkey((u_char *) keybuf, &local))
return NULL;
}
memcpy(output, setting, 9);
output[9] = '\0';
p = (u_char *) output + 9;
} else {
/*
* "old"-style:
* setting - 2 chars of salt
* key - up to 8 characters
*/
count = 25;
if (ascii_is_unsafe(setting[0]) || ascii_is_unsafe(setting[1]))
return NULL;
salt = (ascii_to_bin(setting[1]) << 6)
| ascii_to_bin(setting[0]);
output[0] = setting[0];
output[1] = setting[1];
p = (u_char *) output + 2;
}
setup_salt(salt, &local);
/*
* Do it.
*/
if (do_des(0, 0, &r0, &r1, count, &local))
return NULL;
/*
* Now encode the result...
*/
l = (r0 >> 8);
*p++ = ascii64[(l >> 18) & 0x3f];
*p++ = ascii64[(l >> 12) & 0x3f];
*p++ = ascii64[(l >> 6) & 0x3f];
*p++ = ascii64[l & 0x3f];
l = (r0 << 16) | ((r1 >> 16) & 0xffff);
*p++ = ascii64[(l >> 18) & 0x3f];
*p++ = ascii64[(l >> 12) & 0x3f];
*p++ = ascii64[(l >> 6) & 0x3f];
*p++ = ascii64[l & 0x3f];
l = r1 << 2;
*p++ = ascii64[(l >> 12) & 0x3f];
*p++ = ascii64[(l >> 6) & 0x3f];
*p++ = ascii64[l & 0x3f];
*p = 0;
return output;
}
static char *
_crypt_extended(const char *key, const char *setting)
{
static char output[21];
return _crypt_extended_r(key, setting, output);
}
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: FreeSec crypt()
2012-06-13 1:18 ` Rich Felker
@ 2012-06-13 6:10 ` Szabolcs Nagy
2012-06-13 12:43 ` Solar Designer
2012-06-13 12:58 ` Rich Felker
2012-06-13 12:07 ` Solar Designer
1 sibling, 2 replies; 17+ messages in thread
From: Szabolcs Nagy @ 2012-06-13 6:10 UTC (permalink / raw)
To: musl
* Rich Felker <dalias@aerifal.cx> [2012-06-12 21:18:42 -0400]:
> On Wed, Jun 13, 2012 at 03:51:13AM +0400, Solar Designer wrote:
> > Rich -
> >
> > As discussed on IRC, here is a revision of the FreeSec crypt() code with
>
> Thanks. Here's a _really_ quick draft, untested, of the direction I
> wanted to take it with making the tables static-initialized. Note that
my comments:
> #include <sys/types.h>
> #include <string.h>
>
> struct _crypt_extended_local {
> u_int32_t saltbits;
> u_int32_t en_keysl[16], en_keysr[16];
> };
>
-#include <sys/types.h>
+#include <stdint.h>
s/u_int32_t/uint32_t/g
s/u_char/unsigned char/g
> static inline int
> ascii_to_bin(int ch)
> {
> int sch = ch>127 ? -(256-ch) : ch;
> int retval;
>
> retval = sch - '.';
> if (sch >= 'A') {
> retval = sch - ('A' - 12);
> if (sch >= 'a')
> retval = sch - ('a' - 38);
> }
> retval &= 0x3f;
>
> return retval;
> }
>
s/inline//
on [-128,255] the following code gives the same result:
static int ascii_to_bin2(int c)
{
if (c >= 128)
c += -128 + 18;
else if (c >= 97)
c += -97 + 38;
else if (c >= 65)
c += -65 + 12;
else
c += 128 + 18;
return (unsigned)c % 64;
}
> char *
> _crypt_extended_r(const char *key, const char *setting, char *output)
> {
...
> while (q - (u_char *) keybuf < sizeof(keybuf)) {
> *q++ = *key << 1;
implementation-defined signed shift
> for (i = 1, count = 0; i < 5; i++) {
> int value = ascii_to_bin(setting[i]);
> if (ascii64[value] != setting[i])
> return NULL;
> count |= value << (i - 1) * 6;
> }
signed shift (harmless)
> while (q - (u_char *) keybuf < sizeof(keybuf) && *key)
> *q++ ^= *key++ << 1;
signed shift
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: FreeSec crypt()
2012-06-13 1:18 ` Rich Felker
2012-06-13 6:10 ` Szabolcs Nagy
@ 2012-06-13 12:07 ` Solar Designer
2012-06-13 14:53 ` Rich Felker
1 sibling, 1 reply; 17+ messages in thread
From: Solar Designer @ 2012-06-13 12:07 UTC (permalink / raw)
To: musl
On Tue, Jun 12, 2012 at 09:18:42PM -0400, Rich Felker wrote:
> Thanks. Here's a _really_ quick draft, untested, of the direction I
> wanted to take it with making the tables static-initialized. Note that
> doing so allowed removing all of the table-creation code and most of
> the existing tables. For me, it's weighing in at ~12k.
This sounds good, yet it's an increase from ~5k for the version I posted
(~6k with tests). I understand that you're avoiding having memory pages
that would be written to by each DES-crypt-using process and thus not
shared - but that would only happen when this code is actually used,
which I think it usually won't be (this is backwards compatibility
stuff; we need to introduce modern crypt() flavors for actual use).
That said, the decision is yours to make, and you appear to have made it.
> I also removed
> some unused code for things like keeping salt/keys between multiple
> runs since the data is not preserved across multiple runs anyway,
It can be preserved if you make the (tiny) struct _crypt_extended_local
static.
> and the lookup tables for bitshifts.
As discussed on IRC, I had tried that, but reverted my changes because
they resulted in code size increase (greater than the savings from not
having those tables). Apparently, the table lookups helped avoid mov's
(on 2-operand archs like x86) and add/sub (becomes part of effective
address calculation). Did you check how this affected total size in
your case? Or do you prefer cleaner source code anyway (makes sense)?
> > Also, we could want to add a runtime self-test, which would detect
> > possible miscompiles.
>
> I understand your motivation for doing this with security-critical
> things, but really most/all of libc is security-critical, and we can't
> have runtime miscompilation tests all over the place. Moreover, the
> vast majority of cases of GCC "miscompiling" something turn out to be
> code that's invoking undefined behavior; the only non-UB example I've
> encountered while working on musl is gcc 4.7's bad breakage, which is
> so bad you can't even get programs to start...
I agree that the vast majority of cases may involve UB, but so what - we
can't be 100% certain we don't have any cases of UB in our source code
even if we review it very carefully. We might miss things, and besides
source code changes over time may introduce UB (e.g., changes in
variable declarations may result in code that continues to work
correctly, but actually depends on undefined behavior).
We have a fairly large chunk of code here (a few KB), which we can have
self-tested by a few hundred bytes of code more. I think this is worth
it. Besides, the self-test may serve to zeroize sensitive data - and in
a more reliable way than a memset() would (which may be optimized out,
and it would not necessarily zeroize stack and registers). In fact, I
am using this approach to zeroization in crypt_blowfish. Yes, the
self-test needs to run _after_ hashing the real password, and then
depending on self-test result you either return the originally computed
value or you return an error indication (what to return from crypt() on
error is a separate non-trivial topic).
> * This version is derived from the original implementation of FreeSec
...
Can you please add a comment documenting your changes, too?
I notice that you fully dropped the tests - are you going to have
compile-time tests elsewhere?
Thanks,
Alexander
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: FreeSec crypt()
2012-06-13 6:10 ` Szabolcs Nagy
@ 2012-06-13 12:43 ` Solar Designer
2012-06-13 12:58 ` Rich Felker
1 sibling, 0 replies; 17+ messages in thread
From: Solar Designer @ 2012-06-13 12:43 UTC (permalink / raw)
To: musl
On Wed, Jun 13, 2012 at 08:10:32AM +0200, Szabolcs Nagy wrote:
> static int ascii_to_bin2(int c)
> {
> if (c >= 128)
> c += -128 + 18;
> else if (c >= 97)
> c += -97 + 38;
> else if (c >= 65)
> c += -65 + 12;
> else
> c += 128 + 18;
> return (unsigned)c % 64;
> }
I think we should use a lookup table instead, which would also reduce
the timing leaks we have here. Salts are not secret (not any more than
the hashes), but they're not supposed to be known to an attacker in
advance (before the hashes are possibly leaked/stolen) and knowing them
(but not yet the hashes) may enable char-by-char timing attacks on
hash encoding comparisons (thereby leaking the hashes after _many_
tries). This is almost purely theoretical for a number of reasons,
yet if we strive for perfection, we should do the right thing in this
respect as well.
Perhaps the same lookup table should also replace ascii_is_unsafe() by
returning a value outside of the 0 .. 63 range in the unsafe cases.
We'd need to check for such out of range values, then.
Thank you for your comments!
Alexander
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: FreeSec crypt()
2012-06-13 6:10 ` Szabolcs Nagy
2012-06-13 12:43 ` Solar Designer
@ 2012-06-13 12:58 ` Rich Felker
2012-06-13 13:18 ` Solar Designer
1 sibling, 1 reply; 17+ messages in thread
From: Rich Felker @ 2012-06-13 12:58 UTC (permalink / raw)
To: musl
On Wed, Jun 13, 2012 at 08:10:32AM +0200, Szabolcs Nagy wrote:
> > char *
> > _crypt_extended_r(const char *key, const char *setting, char *output)
> > {
> ....
> > while (q - (u_char *) keybuf < sizeof(keybuf)) {
> > *q++ = *key << 1;
>
> implementation-defined signed shift
Undefined. Right shifts are implementation-defined. Left-shifts are
defined only for positive operands that don't overflow.
Note that even if the behavior were defined, this code seems to have
different behavior for high bytes depending on the signedness of char.
That looks like a major bug; I thought that bug in crypt
implementations was fixed years ago.
> > for (i = 1, count = 0; i < 5; i++) {
> > int value = ascii_to_bin(setting[i]);
> > if (ascii64[value] != setting[i])
> > return NULL;
> > count |= value << (i - 1) * 6;
> > }
>
> signed shift (harmless)
Yes this one seems to be harmless unless it can overflow, and from the
loop bounds it seems impossible to overflow.
> > while (q - (u_char *) keybuf < sizeof(keybuf) && *key)
> > *q++ ^= *key++ << 1;
>
> signed shift
This one looks like it has the same bug as the first.
Rich
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: FreeSec crypt()
2012-06-13 12:58 ` Rich Felker
@ 2012-06-13 13:18 ` Solar Designer
2012-06-13 14:56 ` Rich Felker
0 siblings, 1 reply; 17+ messages in thread
From: Solar Designer @ 2012-06-13 13:18 UTC (permalink / raw)
To: musl
On Wed, Jun 13, 2012 at 08:58:39AM -0400, Rich Felker wrote:
> On Wed, Jun 13, 2012 at 08:10:32AM +0200, Szabolcs Nagy wrote:
> > > while (q - (u_char *) keybuf < sizeof(keybuf)) {
> > > *q++ = *key << 1;
> >
> > implementation-defined signed shift
>
> Undefined. Right shifts are implementation-defined. Left-shifts are
> defined only for positive operands that don't overflow.
Right. I'm going to fix that.
> Note that even if the behavior were defined, this code seems to have
> different behavior for high bytes depending on the signedness of char.
Do you mean high bits (not bytes)? Why would signedness of char matter
if the behavior of the signed char overflowing left shift were defined?
Alexander
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: FreeSec crypt()
2012-06-13 12:07 ` Solar Designer
@ 2012-06-13 14:53 ` Rich Felker
2012-06-24 7:21 ` Solar Designer
0 siblings, 1 reply; 17+ messages in thread
From: Rich Felker @ 2012-06-13 14:53 UTC (permalink / raw)
To: musl
On Wed, Jun 13, 2012 at 04:07:54PM +0400, Solar Designer wrote:
> > I also removed
> > some unused code for things like keeping salt/keys between multiple
> > runs since the data is not preserved across multiple runs anyway,
>
> It can be preserved if you make the (tiny) struct _crypt_extended_local
> static.
I suppose this is worth considering. I was assuming it would be
difficult to preserve (require otherwise-unneeded locking), but for
crypt_r each caller could be responsible for its own copy.
However, on the other hand I'm not sure I see the benefit. Why would
you call crypt or crypt_r multiple times with the same key/salt except
possibly for password cracking (in which case you'll want a highly
optimized-for-speed implementation)?
> > and the lookup tables for bitshifts.
>
> As discussed on IRC, I had tried that, but reverted my changes because
> they resulted in code size increase (greater than the savings from not
> having those tables). Apparently, the table lookups helped avoid mov's
> (on 2-operand archs like x86) and add/sub (becomes part of effective
> address calculation). Did you check how this affected total size in
> your case? Or do you prefer cleaner source code anyway (makes sense)?
I didn't compare, but yes I do prefer cleaner source. I'm a bit
surprised that you found the difference in code size to be >136 bytes
though. Are you sure the code size changed by that much?
> > > Also, we could want to add a runtime self-test, which would detect
> > > possible miscompiles.
> >
> > I understand your motivation for doing this with security-critical
> > things, but really most/all of libc is security-critical, and we can't
> > have runtime miscompilation tests all over the place. Moreover, the
> > vast majority of cases of GCC "miscompiling" something turn out to be
> > code that's invoking undefined behavior; the only non-UB example I've
> > encountered while working on musl is gcc 4.7's bad breakage, which is
> > so bad you can't even get programs to start...
>
> I agree that the vast majority of cases may involve UB, but so what - we
> can't be 100% certain we don't have any cases of UB in our source code
> even if we review it very carefully.
For purely computational code that doesn't recurse or loop arbitrarily
long based on the input or read and write all over memory, static
analysis can determine the absence of UB. Having no UB, and having the
code tested with both signed and unsigned char (easy with gcc -f
options) should give an extremely high level of confidence that cases
which have been tested on one system/compiler will behave identically
on another system or another compiler.
> We might miss things, and besides
> source code changes over time may introduce UB (e.g., changes in
> variable declarations may result in code that continues to work
> correctly, but actually depends on undefined behavior).
And the same is true elsewhere in much more critical code, like
snprintf, strcpy, strchr, etc. all of which could create huge vulns if
miscompiled. What I was saying is that if you're going to call into
question the compiler, I think you need some basis for deciding which
functions need to double-check that their results are correct, unless
your intent is to make ALL of your code fault-tolerant in the form of
double-checking its results. The latter would certainly be an
interesting project in itself, but I think it goes way beyond the
scope (and contrary to many of the goals, including size, speed, and
simplicity) of musl. If one really wants to make such a system, I
think it would make a lot more sense to have the checking
automatically generated by the compiler/toolchain (e.g. use 2 separate
compilers and compare the results constantly).
> We have a fairly large chunk of code here (a few KB), which we can have
> self-tested by a few hundred bytes of code more. I think this is worth
> it.
I'm open to seeing them if they're really that small and non-invasive.
> Besides, the self-test may serve to zeroize sensitive data - and in
> a more reliable way than a memset() would (which may be optimized out,
> and it would not necessarily zeroize stack and registers). In fact, I
> am using this approach to zeroization in crypt_blowfish. Yes, the
> self-test needs to run _after_ hashing the real password, and then
> depending on self-test result you either return the originally computed
> value or you return an error indication (what to return from crypt() on
> error is a separate non-trivial topic).
I saw the notes on this. What real-world code breaks from the
conformant behavior?
> > * This version is derived from the original implementation of FreeSec
> ....
>
> Can you please add a comment documenting your changes, too?
Sure, I'll do that before committing. What I sent to the list was just
a quick draft, and I certainly don't want to misrepresent my modified
version as if it were your original, especially if it has bugs. I
really should have added a comment before even sending it...
> I notice that you fully dropped the tests - are you going to have
> compile-time tests elsewhere?
I just did it while shuffling around the code -- I think I moved them
and the adjacent table-gen code I wrote to a separate file at the same
time. I'm fairly indifferent to putting them in the file, but I'd much
rather have a test for the external API in an external test module as
the actual tests we use.
Rich
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: FreeSec crypt()
2012-06-13 13:18 ` Solar Designer
@ 2012-06-13 14:56 ` Rich Felker
2012-06-13 16:45 ` Solar Designer
0 siblings, 1 reply; 17+ messages in thread
From: Rich Felker @ 2012-06-13 14:56 UTC (permalink / raw)
To: musl
On Wed, Jun 13, 2012 at 05:18:07PM +0400, Solar Designer wrote:
> > Note that even if the behavior were defined, this code seems to have
> > different behavior for high bytes depending on the signedness of char.
>
> Do you mean high bits (not bytes)?
"High bytes" is a poorly defined term I used to mean bytes with their
high bit set, or bytes outside the ASCII range, etc.
> Why would signedness of char matter
> if the behavior of the signed char overflowing left shift were defined?
Well if char is signed, (char)0x80 << 1 is -256. If char is unsigned,
(char)0x80 << 1 is 256.
Rich
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: FreeSec crypt()
2012-06-13 14:56 ` Rich Felker
@ 2012-06-13 16:45 ` Solar Designer
2012-06-13 17:27 ` Rich Felker
2012-06-13 17:32 ` Szabolcs Nagy
0 siblings, 2 replies; 17+ messages in thread
From: Solar Designer @ 2012-06-13 16:45 UTC (permalink / raw)
To: musl
On Wed, Jun 13, 2012 at 10:56:03AM -0400, Rich Felker wrote:
> On Wed, Jun 13, 2012 at 05:18:07PM +0400, Solar Designer wrote:
> > > Note that even if the behavior were defined, this code seems to have
> > > different behavior for high bytes depending on the signedness of char.
...
> > Why would signedness of char matter
> > if the behavior of the signed char overflowing left shift were defined?
>
> Well if char is signed, (char)0x80 << 1 is -256. If char is unsigned,
> (char)0x80 << 1 is 256.
Sure, but we had:
const char *key;
u_char *q;
*q++ = *key << 1;
so while *key << 1 is either -256 or 256 (promoted to int or unsigned
int), those high bits get dropped on the assignment to *q anyway,
resulting in the same value there either way. No?
Alexander
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: FreeSec crypt()
2012-06-13 16:45 ` Solar Designer
@ 2012-06-13 17:27 ` Rich Felker
2012-06-13 17:32 ` Szabolcs Nagy
1 sibling, 0 replies; 17+ messages in thread
From: Rich Felker @ 2012-06-13 17:27 UTC (permalink / raw)
To: musl
On Wed, Jun 13, 2012 at 08:45:46PM +0400, Solar Designer wrote:
> On Wed, Jun 13, 2012 at 10:56:03AM -0400, Rich Felker wrote:
> > On Wed, Jun 13, 2012 at 05:18:07PM +0400, Solar Designer wrote:
> > > > Note that even if the behavior were defined, this code seems to have
> > > > different behavior for high bytes depending on the signedness of char.
> ....
> > > Why would signedness of char matter
> > > if the behavior of the signed char overflowing left shift were defined?
> >
> > Well if char is signed, (char)0x80 << 1 is -256. If char is unsigned,
> > (char)0x80 << 1 is 256.
>
> Sure, but we had:
>
> const char *key;
> u_char *q;
> *q++ = *key << 1;
>
> so while *key << 1 is either -256 or 256 (promoted to int or unsigned
> int), those high bits get dropped on the assignment to *q anyway,
> resulting in the same value there either way. No?
You're right on that. Ideally the functions should just take arguments
of type unsigned char *, and the crypt/crypt_r wrapper should cast the
original char * to unsigned char *. This is the same way all the
standard string functions (like strcmp) are required to work.
Casting/converting the _value_ after reading it also happens to work,
and is sufficient for musl's purposes (we assume, per POSIX, that
CHAR_BIT is 8, but also that signed types are twos complement), but
only reinterpreting by casting the pointer before reading it is 100%
portable. On a non-twos-complement machine, reading a signed char is
lossy (it can only obtain 255 possible values, not 256).
Rich
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: FreeSec crypt()
2012-06-13 16:45 ` Solar Designer
2012-06-13 17:27 ` Rich Felker
@ 2012-06-13 17:32 ` Szabolcs Nagy
2012-06-13 17:36 ` Rich Felker
1 sibling, 1 reply; 17+ messages in thread
From: Szabolcs Nagy @ 2012-06-13 17:32 UTC (permalink / raw)
To: musl
* Solar Designer <solar@openwall.com> [2012-06-13 20:45:46 +0400]:
> On Wed, Jun 13, 2012 at 10:56:03AM -0400, Rich Felker wrote:
> > Well if char is signed, (char)0x80 << 1 is -256. If char is unsigned,
> > (char)0x80 << 1 is 256.
>
> Sure, but we had:
>
> const char *key;
> u_char *q;
> *q++ = *key << 1;
>
> so while *key << 1 is either -256 or 256 (promoted to int or unsigned
> int), those high bits get dropped on the assignment to *q anyway,
> resulting in the same value there either way. No?
yes the code happens to work whenever -128<<1 is -256
and i assume -256 is what most compilers will give
usually in case of two's complement int representation
but -128<<1 is UB and should be fixed anyway
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: FreeSec crypt()
2012-06-13 17:32 ` Szabolcs Nagy
@ 2012-06-13 17:36 ` Rich Felker
0 siblings, 0 replies; 17+ messages in thread
From: Rich Felker @ 2012-06-13 17:36 UTC (permalink / raw)
To: musl
On Wed, Jun 13, 2012 at 07:32:48PM +0200, Szabolcs Nagy wrote:
> * Solar Designer <solar@openwall.com> [2012-06-13 20:45:46 +0400]:
> > On Wed, Jun 13, 2012 at 10:56:03AM -0400, Rich Felker wrote:
> > > Well if char is signed, (char)0x80 << 1 is -256. If char is unsigned,
> > > (char)0x80 << 1 is 256.
> >
> > Sure, but we had:
> >
> > const char *key;
> > u_char *q;
> > *q++ = *key << 1;
> >
> > so while *key << 1 is either -256 or 256 (promoted to int or unsigned
> > int), those high bits get dropped on the assignment to *q anyway,
> > resulting in the same value there either way. No?
>
> yes the code happens to work whenever -128<<1 is -256
>
> and i assume -256 is what most compilers will give
> usually in case of two's complement int representation
>
> but -128<<1 is UB and should be fixed anyway
Note that x<<1 is always equal to x*2 when both are defined, and the
latter is defined in our case since the range of x is much smaller
than half the range of int. So if the underlying pointer type issue
isn't fixed, just changing <<1 to *2 would work.
In general, portable code wanting to use x<<n with negative values of
x could replace it with x*(1<<n) and hope the compiler is smart enough
to generate code equivalent to the traditional behavior of x<<n (i.e.
hope it can apply the associativity to * and <<).
Rich
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: FreeSec crypt()
2012-06-13 14:53 ` Rich Felker
@ 2012-06-24 7:21 ` Solar Designer
2012-06-24 7:32 ` Solar Designer
2012-06-25 3:51 ` Rich Felker
0 siblings, 2 replies; 17+ messages in thread
From: Solar Designer @ 2012-06-24 7:21 UTC (permalink / raw)
To: musl
[-- Attachment #1: Type: text/plain, Size: 4594 bytes --]
On Wed, Jun 13, 2012 at 10:53:18AM -0400, Rich Felker wrote:
> On Wed, Jun 13, 2012 at 04:07:54PM +0400, Solar Designer wrote:
> > > I also removed
> > > some unused code for things like keeping salt/keys between multiple
> > > runs since the data is not preserved across multiple runs anyway,
> >
> > It can be preserved if you make the (tiny) struct _crypt_extended_local
> > static.
>
> I suppose this is worth considering. I was assuming it would be
> difficult to preserve (require otherwise-unneeded locking), but for
> crypt_r each caller could be responsible for its own copy.
>
> However, on the other hand I'm not sure I see the benefit. Why would
> you call crypt or crypt_r multiple times with the same key/salt except
> possibly for password cracking (in which case you'll want a highly
> optimized-for-speed implementation)?
You're right. Additionally, preserving this requires that we keep
sensitive data around (from the previous password hashed). I've dropped
this stuff now.
> > > and the lookup tables for bitshifts.
> >
> > As discussed on IRC, I had tried that, but reverted my changes because
> > they resulted in code size increase (greater than the savings from not
> > having those tables). Apparently, the table lookups helped avoid mov's
> > (on 2-operand archs like x86) and add/sub (becomes part of effective
> > address calculation). Did you check how this affected total size in
> > your case? Or do you prefer cleaner source code anyway (makes sense)?
>
> I didn't compare, but yes I do prefer cleaner source. I'm a bit
> surprised that you found the difference in code size to be >136 bytes
> though. Are you sure the code size changed by that much?
Yes, and I was surprised too. However, I've re-introduced those changes
now, and along with other changes I made there appears to be almost no
size increase from them.
> > > > Also, we could want to add a runtime self-test, which would detect
> > > > possible miscompiles.
> > >
> > > I understand your motivation for doing this with security-critical
> > > things, but really most/all of libc is security-critical, and we can't
> > > have runtime miscompilation tests all over the place. Moreover, the
> > > vast majority of cases of GCC "miscompiling" something turn out to be
> > > code that's invoking undefined behavior; the only non-UB example I've
> > > encountered while working on musl is gcc 4.7's bad breakage, which is
> > > so bad you can't even get programs to start...
> >
> > I agree that the vast majority of cases may involve UB, but so what - we
> > can't be 100% certain we don't have any cases of UB in our source code
> > even if we review it very carefully.
>
> For purely computational code that doesn't recurse or loop arbitrarily
> long based on the input or read and write all over memory, static
> analysis can determine the absence of UB.
Are you performing such static analysis on musl?
> > We have a fairly large chunk of code here (a few KB), which we can have
> > self-tested by a few hundred bytes of code more. I think this is worth
> > it.
>
> I'm open to seeing them if they're really that small and non-invasive.
I've added a runtime self-test now. The cost appears to be 200 to 300
bytes of code and read-only data.
Another reason to have this for crypt() when we don't have it for many
other functions is that it is more difficult to recover from improperly
hashed passwords (than from some other bug in another libc interface).
Rather than just fix the bug, we might have to add backwards
compatibility code. Even worse, those improperly computed hashes may be
a security risk that is not necessarily avoided by simply installing
fixed software.
> > value or you return an error indication (what to return from crypt() on
> > error is a separate non-trivial topic).
>
> I saw the notes on this. What real-world code breaks from the
> conformant behavior?
I think the majority of daemons, etc. that do authentication with
crypt() don't handle possible NULL returns. This is just starting to
change now. They don't really break under normal conditions because
normally crypt() returns the hashed password and not NULL; but if it
does somehow return NULL (e.g., because the salt read from the shadow
file is invalid), then I'd expect most users of crypt() to crash.
...Attached is my latest revision of crypt_freesec. I've reduced the
table sizes even further (7 KB, may be precomputed) and I made certain
other changes as discussed. I'd appreciate another review, and some
fuzzing against another implementation wouldn't hurt.
Alexander
[-- Attachment #2: crypt_freesec.h --]
[-- Type: text/plain, Size: 2493 bytes --]
/*
* The following notice applies to this header file (only):
*
* Copyright (c) 2002,2010,2012 Solar Designer <solar at openwall.com>
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted.
*/
#ifndef _CRYPT_FREESEC_H
#define _CRYPT_FREESEC_H
struct _crypt_extended_local {
unsigned char output[21];
};
struct _crypt_extended_shared {
uint32_t psbox[8][64];
uint32_t ip_maskl[16][16], ip_maskr[16][16];
uint32_t fp_maskl[8][16], fp_maskr[8][16];
uint32_t key_perm_maskl[8][16], key_perm_maskr[12][16];
uint32_t comp_maskl0[4][8], comp_maskr0[4][8];
uint32_t comp_maskl1[4][16], comp_maskr1[4][16];
};
/*
* _crypt_extended_init() must be called explicitly before first use of
* _crypt_extended_r(). Strictly speaking, _crypt_extended_init() is not
* reentrant unless the "shared" struct happens to be private to each call.
* All it does is initialize some variables inside the "shared" struct to
* constant values, so it is unlikely that anything would go wrong if this is
* done multiple times in parallel, but correct behavior in that case is not
* guaranteed (e.g., things may go wrong if a given CPU architecture can't
* operate on 32-bit quantities natively, requiring read-modify-write
* instruction sequences operating on larger quantities and thus affecting
* nearby array elements).
*
* After _crypt_extended_init() has returned, the resulting "shared" struct
* may in fact be safely shared between different threads' calls to
* _crypt_extended_r(), which is in fact reentrant (but each concurrent call
* must use its own instance of the "local" struct).
*
* _crypt_extended_r() returns NULL on error. Although modern standards say
* that crypt(3) does in fact return NULL on error, many applications do not
* expect that. Thus, it is recommended that a crypt(3)-like wrapper function
* translate these NULL returns into strings guaranteed to be different from
* the "setting" string, too short for matching a valid password hash, and not
* containing any characters that would be special for the passwd file format.
* Specifically, such a wrapper function may return "*0" on error as long as
* the "setting" string does not start with "*0", or "*1" otherwise.
*/
void _crypt_extended_init(struct _crypt_extended_shared *shared);
char *_crypt_extended_r(const char *key, const char *setting,
struct _crypt_extended_local *local,
const struct _crypt_extended_shared *shared);
#endif
[-- Attachment #3: crypt_freesec.c --]
[-- Type: text/plain, Size: 22332 bytes --]
/*
* This version is derived from the original implementation of FreeSec
* (release 1.1) by David Burren. I've made it reentrant, reduced its memory
* usage from about 70 KB to about 7 KB (with only minimal performance impact
* and keeping code size about the same), made the handling of invalid salts
* mostly UFC-crypt compatible, added a quick runtime self-test (which also
* serves to zeroize the stack from sensitive data), and added optional tests.
* - Solar Designer <solar at openwall.com>
*/
/*
* FreeSec: libcrypt for NetBSD
*
* Copyright (c) 1994 David Burren
* Copyright (c) 2000,2002,2010,2012 Solar Designer
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* 3. Neither the name of the author nor the names of other contributors
* may be used to endorse or promote products derived from this software
* without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*
* $Owl: Owl/packages/glibc/crypt_freesec.c,v 1.6 2010/02/20 14:45:06 solar Exp $
* $Id: crypt.c,v 1.15 1994/09/13 04:58:49 davidb Exp $
*
* This is an original implementation of the DES and the crypt(3) interfaces
* by David Burren. It has been heavily re-worked by Solar Designer.
*/
#include <stdint.h>
#include <string.h>
#ifdef DEBUG
#include <assert.h>
#endif
#ifdef TEST
#include <stdio.h>
#endif
#include "crypt_freesec.h"
struct expanded_key {
uint32_t l[16], r[16];
};
#define _PASSWORD_EFMT1 '_'
static const unsigned char IP[64] = {
58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20, 12, 4,
62, 54, 46, 38, 30, 22, 14, 6, 64, 56, 48, 40, 32, 24, 16, 8,
57, 49, 41, 33, 25, 17, 9, 1, 59, 51, 43, 35, 27, 19, 11, 3,
61, 53, 45, 37, 29, 21, 13, 5, 63, 55, 47, 39, 31, 23, 15, 7
};
static const unsigned char key_perm[56] = {
57, 49, 41, 33, 25, 17, 9, 1, 58, 50, 42, 34, 26, 18,
10, 2, 59, 51, 43, 35, 27, 19, 11, 3, 60, 52, 44, 36,
63, 55, 47, 39, 31, 23, 15, 7, 62, 54, 46, 38, 30, 22,
14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 28, 20, 12, 4
};
static const unsigned char key_shifts[16] = {
1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1
};
static const unsigned char comp_perm[48] = {
14, 17, 11, 24, 1, 5, 3, 28, 15, 6, 21, 10,
23, 19, 12, 4, 26, 8, 16, 7, 27, 20, 13, 2,
41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48,
44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32
};
/*
* No E box is used, as it's replaced by some ANDs, shifts, and ORs.
*/
static const unsigned char sbox[8][64] = {
{
14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7,
0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8,
4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0,
15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13
},
{
15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10,
3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5,
0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15,
13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9
},
{
10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8,
13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1,
13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7,
1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12
},
{
7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15,
13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9,
10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4,
3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14
},
{
2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9,
14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6,
4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14,
11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3
},
{
12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11,
10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8,
9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6,
4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13
},
{
4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1,
13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6,
1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2,
6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12
},
{
13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7,
1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2,
7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8,
2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11
}
};
static const unsigned char pbox[32] = {
16, 7, 20, 21, 29, 12, 28, 17, 1, 15, 23, 26, 5, 18, 31, 10,
2, 8, 24, 14, 32, 27, 3, 9, 19, 13, 30, 6, 22, 11, 4, 25
};
static const unsigned char ascii64[] =
"./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
/* 0000000000111111111122222222223333333333444444444455555555556666 */
/* 0123456789012345678901234567890123456789012345678901234567890123 */
/*
* We match the behavior of UFC-crypt on systems where "char" is signed by
* default (the majority), regardless of char's signedness on our system.
*/
static uint32_t ascii_to_bin(int ch)
{
int sch = (ch < 0x80) ? ch : -(0x100 - ch);
int retval;
retval = sch - '.';
if (sch >= 'A') {
retval = sch - ('A' - 12);
if (sch >= 'a')
retval = sch - ('a' - 38);
}
retval &= 0x3f;
return retval;
}
/*
* When we choose to "support" invalid salts, nevertheless disallow those
* containing characters that would violate the passwd file format.
*/
static inline int ascii_is_unsafe(unsigned char ch)
{
return !ch || ch == '\n' || ch == ':';
}
static void init_ip_k(struct _crypt_extended_shared *shared)
{
unsigned int i, j, k, ibit, obit;
uint32_t il, ir, fl, fr;
unsigned char inv_key_perm[64];
unsigned char inv_comp_perm[56];
unsigned char init_perm[64], final_perm[64];
/*
* Set up the initial & final permutations into a useful form, and
* initialise the inverted key permutation.
*/
for (i = 0; i < 64; i++) {
init_perm[final_perm[i] = IP[i] - 1] = i;
inv_key_perm[i] = 255;
}
/*
* Invert the key permutation and initialise the inverted key
* compression permutation.
*/
for (i = 0; i < 56; i++) {
inv_key_perm[key_perm[i] - 1] = i;
inv_comp_perm[i] = 255;
}
/*
* Invert the key compression permutation.
*/
for (i = 0; i < 48; i++) {
inv_comp_perm[comp_perm[i] - 1] = i;
}
/*
* Set up the OR-mask arrays for the initial and final permutations,
* and for the key initial and compression permutations.
*/
for (k = 0; k < 16; k++) {
for (i = 0; i < 16; i++) {
il = ir = fl = fr = 0;
for (j = 0; j < 4; j++) {
ibit = 4 * k + j;
if (i & (8 >> j)) {
if ((obit = init_perm[ibit]) < 32)
il |= 0x80000000 >> obit;
else
ir |= 0x80000000 >> (obit - 32);
if ((obit = final_perm[ibit]) < 32)
fl |= 0x80000000 >> obit;
else
fr |= 0x80000000 >> (obit - 32);
}
}
shared->ip_maskl[k][i] = il;
shared->ip_maskr[k][i] = ir;
if (k & 1) {
shared->fp_maskl[k >> 1][i] = fl;
#ifdef DEBUG
assert(!fr);
#endif
} else {
shared->fp_maskr[k >> 1][i] = fr;
#ifdef DEBUG
assert(!fl);
#endif
}
il = ir = 0;
for (j = 0; j < 4 - (k & 1); j++) {
ibit = 4 * k + j;
if (i & (8 >> j)) {
if ((obit = inv_key_perm[ibit]) == 255)
continue;
if (obit < 28)
il |= 0x08000000 >> obit;
else
ir |= 0x08000000 >> (obit - 28);
}
}
if (!(k & 1))
shared->key_perm_maskl[k >> 1][i] = il;
#ifdef DEBUG
else
assert(!il);
#endif
if (k < 8)
shared->key_perm_maskr[k][i] = ir;
else if (k & 1)
shared->key_perm_maskr[4 + (k >> 1)][i] = ir;
#ifdef DEBUG
else
assert(!ir);
#endif
}
}
for (k = 0; k < 8; k++) {
for (i = 0; i < 8; i++) {
il = ir = 0;
for (j = 0; j < 3; j++) {
ibit = 7 * k + j;
if (i & (4 >> j)) {
if ((obit = inv_comp_perm[ibit]) == 255)
continue;
if (obit < 24)
il |= 0x00800000 >> obit;
else
ir |= 0x00800000 >> (obit - 24);
}
}
if (k < 4) {
shared->comp_maskl0[k][i] = il;
#ifdef DEBUG
assert(!ir);
#endif
} else {
shared->comp_maskr0[k - 4][i] = ir;
#ifdef DEBUG
assert(!il);
#endif
}
}
for (i = 0; i < 16; i++) {
il = ir = 0;
for (j = 3; j < 7; j++) {
ibit = 7 * k + j;
if (i & (0x40 >> j)) {
if ((obit = inv_comp_perm[ibit]) == 255)
continue;
if (obit < 24)
il |= 0x00800000 >> obit;
else
ir |= 0x00800000 >> (obit - 24);
}
}
if (k < 4) {
shared->comp_maskl1[k][i] = il;
#ifdef DEBUG
assert(!ir);
#endif
} else {
shared->comp_maskr1[k - 4][i] = ir;
#ifdef DEBUG
assert(!il);
#endif
}
}
}
}
static void init_s(struct _crypt_extended_shared *shared)
{
unsigned int i, j, b;
unsigned char u_sbox[8][64];
unsigned char un_pbox[32];
/*
* Invert the S-boxes, reordering the input bits.
*/
for (i = 0; i < 8; i++)
for (j = 0; j < 64; j++) {
b = (j & 0x20) | ((j & 1) << 4) | ((j >> 1) & 0xf);
u_sbox[i][j] = sbox[i][b];
}
/*
* Invert the P-box permutation, and convert into OR-masks for
* handling the output of the S-box arrays setup above.
*/
for (i = 0; i < 32; i++)
un_pbox[pbox[i] - 1] = i;
for (b = 0; b < 8; b++) {
for (i = 0; i < 64; i++) {
uint32_t p = 0;
for (j = 0; j < 4; j++) {
if (u_sbox[b][i] & (8 >> j))
p |= 0x80000000 >> un_pbox[4 * b + j];
}
shared->psbox[b][i] = p;
}
}
}
void _crypt_extended_init(struct _crypt_extended_shared *shared)
{
init_ip_k(shared);
init_s(shared);
}
static uint32_t setup_salt(uint32_t salt)
{
uint32_t obit, saltbit, saltbits;
unsigned int i;
saltbits = 0;
saltbit = 1;
obit = 0x800000;
for (i = 0; i < 24; i++) {
if (salt & saltbit)
saltbits |= obit;
saltbit <<= 1;
obit >>= 1;
}
return saltbits;
}
static void des_setkey(const unsigned char *key, struct expanded_key *ekey,
const struct _crypt_extended_shared *shared)
{
uint32_t k0, k1, rawkey0, rawkey1;
unsigned int shifts, round, i, ibit;
rawkey0 =
(uint32_t)key[3] |
((uint32_t)key[2] << 8) |
((uint32_t)key[1] << 16) |
((uint32_t)key[0] << 24);
rawkey1 =
(uint32_t)key[7] |
((uint32_t)key[6] << 8) |
((uint32_t)key[5] << 16) |
((uint32_t)key[4] << 24);
/*
* Do key permutation and split into two 28-bit subkeys.
*/
k0 = k1 = 0;
for (i = 0, ibit = 28; i < 4; i++, ibit -= 4) {
unsigned int j = i << 1;
k0 |= shared->key_perm_maskl[i][(rawkey0 >> ibit) & 0xf] |
shared->key_perm_maskl[i + 4][(rawkey1 >> ibit) & 0xf];
k1 |= shared->key_perm_maskr[j][(rawkey0 >> ibit) & 0xf];
ibit -= 4;
k1 |= shared->key_perm_maskr[j + 1][(rawkey0 >> ibit) & 0xf] |
shared->key_perm_maskr[i + 8][(rawkey1 >> ibit) & 0xf];
}
/*
* Rotate subkeys and do compression permutation.
*/
shifts = 0;
for (round = 0; round < 16; round++) {
uint32_t t0, t1;
uint32_t kl, kr;
shifts += key_shifts[round];
t0 = (k0 << shifts) | (k0 >> (28 - shifts));
t1 = (k1 << shifts) | (k1 >> (28 - shifts));
kl = kr = 0;
ibit = 25;
for (i = 0; i < 4; i++) {
kl |= shared->comp_maskl0[i][(t0 >> ibit) & 7];
kr |= shared->comp_maskr0[i][(t1 >> ibit) & 7];
ibit -= 4;
kl |= shared->comp_maskl1[i][(t0 >> ibit) & 0xf];
kr |= shared->comp_maskr1[i][(t1 >> ibit) & 0xf];
ibit -= 3;
}
ekey->l[round] = kl;
ekey->r[round] = kr;
}
}
/*
* l_in, r_in, l_out, and r_out are in pseudo-"big-endian" format.
*/
static void do_des(uint32_t l_in, uint32_t r_in,
uint32_t *l_out, uint32_t *r_out,
uint32_t count, uint32_t saltbits, const struct expanded_key *ekey,
const struct _crypt_extended_shared *shared)
{
uint32_t l, r;
/*
* Do initial permutation (IP).
*/
l = r = 0;
if (l_in | r_in) {
unsigned int i, ibit;
for (i = 0, ibit = 28; i < 8; i++, ibit -= 4) {
l |= shared->ip_maskl[i][(l_in >> ibit) & 0xf] |
shared->ip_maskl[i + 8][(r_in >> ibit) & 0xf];
r |= shared->ip_maskr[i][(l_in >> ibit) & 0xf] |
shared->ip_maskr[i + 8][(r_in >> ibit) & 0xf];
}
}
while (count--) {
/*
* Do each round.
*/
unsigned int round = 16;
const uint32_t *kl = ekey->l;
const uint32_t *kr = ekey->r;
uint32_t f;
while (round--) {
uint32_t r48l, r48r;
/*
* Expand R to 48 bits (simulate the E-box).
*/
r48l = ((r & 0x00000001) << 23)
| ((r & 0xf8000000) >> 9)
| ((r & 0x1f800000) >> 11)
| ((r & 0x01f80000) >> 13)
| ((r & 0x001f8000) >> 15);
r48r = ((r & 0x0001f800) << 7)
| ((r & 0x00001f80) << 5)
| ((r & 0x000001f8) << 3)
| ((r & 0x0000001f) << 1)
| ((r & 0x80000000) >> 31);
/*
* Do salting for crypt() and friends, and
* XOR with the permuted key.
*/
f = (r48l ^ r48r) & saltbits;
r48l ^= f ^ *kl++;
r48r ^= f ^ *kr++;
/*
* Do S-box lookups (which shrink it back to 32 bits)
* and do the P-box permutation at the same time.
*/
f = shared->psbox[0][r48l >> 18]
| shared->psbox[1][(r48l >> 12) & 0x3f]
| shared->psbox[2][(r48l >> 6) & 0x3f]
| shared->psbox[3][r48l & 0x3f]
| shared->psbox[4][r48r >> 18]
| shared->psbox[5][(r48r >> 12) & 0x3f]
| shared->psbox[6][(r48r >> 6) & 0x3f]
| shared->psbox[7][r48r & 0x3f];
/*
* Now that we've permuted things, complete f().
*/
f ^= l;
l = r;
r = f;
}
r = l;
l = f;
}
/*
* Do final permutation (inverse of IP).
*/
{
unsigned int i, ibit;
uint32_t lo, ro;
lo = ro = 0;
for (i = 0, ibit = 28; i < 4; i++, ibit -= 4) {
ro |= shared->fp_maskr[i][(l >> ibit) & 0xf] |
shared->fp_maskr[i + 4][(r >> ibit) & 0xf];
ibit -= 4;
lo |= shared->fp_maskl[i][(l >> ibit) & 0xf] |
shared->fp_maskl[i + 4][(r >> ibit) & 0xf];
}
*l_out = lo;
*r_out = ro;
}
}
static void des_cipher(const unsigned char *in, unsigned char *out,
uint32_t count, uint32_t saltbits, const struct expanded_key *ekey,
const struct _crypt_extended_shared *shared)
{
uint32_t l_out, r_out, rawl, rawr;
rawl =
(uint32_t)in[3] |
((uint32_t)in[2] << 8) |
((uint32_t)in[1] << 16) |
((uint32_t)in[0] << 24);
rawr =
(uint32_t)in[7] |
((uint32_t)in[6] << 8) |
((uint32_t)in[5] << 16) |
((uint32_t)in[4] << 24);
do_des(rawl, rawr, &l_out, &r_out, count, saltbits, ekey, shared);
out[0] = l_out >> 24;
out[1] = l_out >> 16;
out[2] = l_out >> 8;
out[3] = l_out;
out[4] = r_out >> 24;
out[5] = r_out >> 16;
out[6] = r_out >> 8;
out[7] = r_out;
}
static char *_crypt_extended_r_uut(const char *_key, const char *_setting,
struct _crypt_extended_local *local,
const struct _crypt_extended_shared *shared)
{
const unsigned char *key = (const unsigned char *)_key;
const unsigned char *setting = (const unsigned char *)_setting;
struct expanded_key ekey;
union {
unsigned char c[8];
uint32_t i[2];
} keybuf;
unsigned char *p, *q;
uint32_t count, salt, l, r0, r1;
unsigned int i;
/*
* Copy the key, shifting each character left by one bit and padding
* with zeroes.
*/
q = keybuf.c;
while (q <= &keybuf.c[sizeof(keybuf.c) - 1]) {
*q++ = *key << 1;
if (*key)
key++;
}
des_setkey(keybuf.c, &ekey, shared);
if (*setting == _PASSWORD_EFMT1) {
/*
* "new"-style:
* setting - underscore, 4 chars of count, 4 chars of salt
* key - unlimited characters
*/
for (i = 1, count = 0; i < 5; i++) {
uint32_t value = ascii_to_bin(setting[i]);
if (ascii64[value] != setting[i])
return NULL;
count |= value << (i - 1) * 6;
}
if (!count)
return NULL;
for (i = 5, salt = 0; i < 9; i++) {
uint32_t value = ascii_to_bin(setting[i]);
if (ascii64[value] != setting[i])
return NULL;
salt |= value << (i - 5) * 6;
}
while (*key) {
/*
* Encrypt the key with itself.
*/
des_cipher(keybuf.c, keybuf.c, 1, 0, &ekey, shared);
/*
* And XOR with the next 8 characters of the key.
*/
q = keybuf.c;
while (q <= &keybuf.c[sizeof(keybuf.c) - 1] && *key)
*q++ ^= *key++ << 1;
des_setkey(keybuf.c, &ekey, shared);
}
memcpy(local->output, setting, 9);
local->output[9] = '\0';
p = local->output + 9;
} else {
/*
* "old"-style:
* setting - 2 chars of salt
* key - up to 8 characters
*/
count = 25;
if (ascii_is_unsafe(setting[0]) || ascii_is_unsafe(setting[1]))
return NULL;
salt = (ascii_to_bin(setting[1]) << 6)
| ascii_to_bin(setting[0]);
local->output[0] = setting[0];
local->output[1] = setting[1];
p = local->output + 2;
}
/*
* Do it.
*/
do_des(0, 0, &r0, &r1, count, setup_salt(salt), &ekey, shared);
/*
* Now encode the result...
*/
l = (r0 >> 8);
*p++ = ascii64[(l >> 18) & 0x3f];
*p++ = ascii64[(l >> 12) & 0x3f];
*p++ = ascii64[(l >> 6) & 0x3f];
*p++ = ascii64[l & 0x3f];
l = (r0 << 16) | ((r1 >> 16) & 0xffff);
*p++ = ascii64[(l >> 18) & 0x3f];
*p++ = ascii64[(l >> 12) & 0x3f];
*p++ = ascii64[(l >> 6) & 0x3f];
*p++ = ascii64[l & 0x3f];
l = r1 << 2;
*p++ = ascii64[(l >> 12) & 0x3f];
*p++ = ascii64[(l >> 6) & 0x3f];
*p++ = ascii64[l & 0x3f];
*p = 0;
return (char *)local->output;
}
char *_crypt_extended_r(const char *key, const char *setting,
struct _crypt_extended_local *local,
const struct _crypt_extended_shared *shared)
{
const char *test_key = "\x80\xff\x80\x01 "
"\x7f\x81\x80\x80\x0d\x0a\xff\x7f \x81 test";
const char *test_setting = "_0.../9Zz";
const char *test_hash = "_0.../9ZzX7iSJNd21sU";
struct _crypt_extended_local local_test;
char *retval;
const char *p;
if (*setting != _PASSWORD_EFMT1) {
test_setting = "\x80x";
test_hash = "\x80x22/wK52ZKGA";
}
/*
* Hash the supplied password.
*/
retval = _crypt_extended_r_uut(key, setting, local, shared);
/*
* Perform a quick self-test. It is important that we make both calls
* to _crypt_extended_r_uut() from the same scope such that they likely
* use the same stack locations, which makes the second call overwrite
* the first call's sensitive data on the stack and makes it more
* likely that any alignment related issues would be detected.
*/
p = _crypt_extended_r_uut(test_key, test_setting, &local_test, shared);
if (p && !strcmp(p, test_hash))
return retval;
/*
* Should not happen.
*/
return NULL;
}
#ifndef TEST_STATIC
#define TEST_STATIC /* not static */
#endif
#ifdef TEST
static char *_crypt_extended(const char *key, const char *setting)
{
TEST_STATIC int initialized = 0;
TEST_STATIC struct _crypt_extended_shared shared;
/* "local" must be static since it holds our own return value */
static struct _crypt_extended_local local;
if (!initialized) {
memset(&shared, 's', sizeof(shared));
memset(&local, 'l', sizeof(local));
_crypt_extended_init(&shared);
initialized = 1;
}
return _crypt_extended_r(key, setting, &local, &shared);
}
static const struct {
char *hash;
char *pw;
} tests[] = {
/* "new"-style */
{"_J9..CCCCXBrJUJV154M", "U*U*U*U*"},
{"_J9..CCCCXUhOBTXzaiE", "U*U***U"},
{"_J9..CCCC4gQ.mB/PffM", "U*U***U*"},
{"_J9..XXXXvlzQGqpPPdk", "*U*U*U*U"},
{"_J9..XXXXsqM/YSSP..Y", "*U*U*U*U*"},
{"_J9..XXXXVL7qJCnku0I", "*U*U*U*U*U*U*U*U"},
{"_J9..XXXXAj8cFbP5scI", "*U*U*U*U*U*U*U*U*"},
{"_J9..SDizh.vll5VED9g", "ab1234567"},
{"_J9..SDizRjWQ/zePPHc", "cr1234567"},
{"_J9..SDizxmRI1GjnQuE", "zxyDPWgydbQjgq"},
{"_K9..SaltNrQgIYUAeoY", "726 even"},
{"_J9..SDSD5YGyRCr4W4c", ""},
{"_01234567IBjxKliXXRQ", "\xc3\x80" "1234abcd"},
{"_012345678OSGpGQRVHA", "\xc3\x80" "9234abcd"},
/* "old"-style, valid salts */
{"CCNf8Sbh3HDfQ", "U*U*U*U*"},
{"CCX.K.MFy4Ois", "U*U***U"},
{"CC4rMpbg9AMZ.", "U*U***U*"},
{"XXxzOu6maQKqQ", "*U*U*U*U"},
{"SDbsugeBiC58A", ""},
{"./xZjzHv5vzVE", "password"},
{"0A2hXM1rXbYgo", "password"},
{"A9RXdR23Y.cY6", "password"},
{"ZziFATVXHo2.6", "password"},
{"zZDDIZ0NOlPzw", "password"},
{"99PxawtsTfX56", "\xc3\x80" "1234abcd"},
{"99jcVcGxUZOWk", "\xc3\x80" "9234abcd"},
/* "old"-style, "reasonable" invalid salts, UFC-crypt behavior expected */
{"\001\002wyd0KZo65Jo", "password"},
{"a_C10Dk/ExaG.", "password"},
{"~\377.5OTsRVjwLo", "password"},
/* The below are erroneous inputs, so NULL return is expected/required */
{"", ""}, /* no salt */
{" ", ""}, /* setting string is too short */
{"a:", ""}, /* unsafe character */
{"\na", ""}, /* unsafe character */
{"_/......", ""}, /* setting string is too short for its type */
{"_........", ""}, /* zero iteration count */
{"_/!......", ""}, /* invalid character in count */
{"_/......!", ""}, /* invalid character in salt */
{NULL, NULL}
};
int main(void)
{
unsigned int i;
for (i = 0; tests[i].hash; i++) {
char *hash = _crypt_extended(tests[i].pw, tests[i].hash);
if (!hash && strlen(tests[i].hash) < 13)
continue; /* expected failure */
if (hash && !strcmp(hash, tests[i].hash))
continue; /* expected success */
puts("FAILED");
return 1;
}
puts("PASSED");
return 0;
}
#endif
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: FreeSec crypt()
2012-06-24 7:21 ` Solar Designer
@ 2012-06-24 7:32 ` Solar Designer
2012-06-25 3:51 ` Rich Felker
1 sibling, 0 replies; 17+ messages in thread
From: Solar Designer @ 2012-06-24 7:32 UTC (permalink / raw)
To: musl
On Sun, Jun 24, 2012 at 11:21:12AM +0400, Solar Designer wrote:
> struct _crypt_extended_shared {
> uint32_t psbox[8][64];
> uint32_t ip_maskl[16][16], ip_maskr[16][16];
> uint32_t fp_maskl[8][16], fp_maskr[8][16];
> uint32_t key_perm_maskl[8][16], key_perm_maskr[12][16];
> uint32_t comp_maskl0[4][8], comp_maskr0[4][8];
> uint32_t comp_maskl1[4][16], comp_maskr1[4][16];
> };
Actually, we should re-order the first two lines. That is make it:
struct _crypt_extended_shared {
uint32_t ip_maskl[16][16], ip_maskr[16][16];
uint32_t psbox[8][64];
uint32_t fp_maskl[8][16], fp_maskr[8][16];
uint32_t key_perm_maskl[8][16], key_perm_maskr[12][16];
uint32_t comp_maskl0[4][8], comp_maskr0[4][8];
uint32_t comp_maskl1[4][16], comp_maskr1[4][16];
};
That's because IP is not always used (it's only used for "new"-style
hashes, not for "old"-style ones where the initial block is always 0
and thus IP is skipped). When it is used, it's used right before
psbox[] is.
Alexander
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: FreeSec crypt()
2012-06-24 7:21 ` Solar Designer
2012-06-24 7:32 ` Solar Designer
@ 2012-06-25 3:51 ` Rich Felker
2012-06-29 5:25 ` Rich Felker
1 sibling, 1 reply; 17+ messages in thread
From: Rich Felker @ 2012-06-25 3:51 UTC (permalink / raw)
To: musl
On Sun, Jun 24, 2012 at 11:21:12AM +0400, Solar Designer wrote:
> On Wed, Jun 13, 2012 at 10:53:18AM -0400, Rich Felker wrote:
> > However, on the other hand I'm not sure I see the benefit. Why would
> > you call crypt or crypt_r multiple times with the same key/salt except
> > possibly for password cracking (in which case you'll want a highly
> > optimized-for-speed implementation)?
>
> You're right. Additionally, preserving this requires that we keep
> sensitive data around (from the previous password hashed). I've dropped
> this stuff now.
Ah, nice catch!
> > > I agree that the vast majority of cases may involve UB, but so what - we
> > > can't be 100% certain we don't have any cases of UB in our source code
> > > even if we review it very carefully.
> >
> > For purely computational code that doesn't recurse or loop arbitrarily
> > long based on the input or read and write all over memory, static
> > analysis can determine the absence of UB.
>
> Are you performing such static analysis on musl?
Not yet/only to a minimal extent so far.
I haven't spent much time on it, but users/contributors have often
posted clang's analysis outputs for discussion on IRC, and it looks
like a promising direction.
> > > value or you return an error indication (what to return from crypt() on
> > > error is a separate non-trivial topic).
> >
> > I saw the notes on this. What real-world code breaks from the
> > conformant behavior?
>
> I think the majority of daemons, etc. that do authentication with
> crypt() don't handle possible NULL returns. This is just starting to
> change now. They don't really break under normal conditions because
> normally crypt() returns the hashed password and not NULL; but if it
> does somehow return NULL (e.g., because the salt read from the shadow
> file is invalid), then I'd expect most users of crypt() to crash.
Indeed, the first program I checked, dropbear, uses the return value
without checking it. It's rather disheartening that something as
important as authentication code is not checking the return value of
each function that could possibly fail. With TCB shadow especially,
password hashes could be highly invalid...
Anyway, nowhere does POSIX say crypt has to fail at all; as far as I
can tell, it's completely possible and reasonable to make an
implementation that always succeeds even on invalid salt. As long as
you ensure that the output can never be matched, it's probably fine to
do this.
> ....Attached is my latest revision of crypt_freesec. I've reduced the
> table sizes even further (7 KB, may be precomputed) and I made certain
> other changes as discussed. I'd appreciate another review, and some
> fuzzing against another implementation wouldn't hurt.
I put this off until after the release so as not to break anything at
the last minute, but I'll try to get it integrated soon.
Rich
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: FreeSec crypt()
2012-06-25 3:51 ` Rich Felker
@ 2012-06-29 5:25 ` Rich Felker
0 siblings, 0 replies; 17+ messages in thread
From: Rich Felker @ 2012-06-29 5:25 UTC (permalink / raw)
To: musl
On Sun, Jun 24, 2012 at 11:51:03PM -0400, Rich Felker wrote:
> > ....Attached is my latest revision of crypt_freesec. I've reduced the
> > table sizes even further (7 KB, may be precomputed) and I made certain
> > other changes as discussed. I'd appreciate another review, and some
> > fuzzing against another implementation wouldn't hurt.
>
> I put this off until after the release so as not to break anything at
> the last minute, but I'll try to get it integrated soon.
I've committed a modified version (with a comment explaining that it's
modified, this time :) to the musl git repo. It's using static
initialized tables instead of runtime generation on the stack. Despite
it being mildly controversial, I left in the runtime test for now,
mainly since it serves the double purpose of clearing potentially
sensitive data from the stack in a clever way without much additional
cost.
I did not commit the standalone tests in-tree, but I did run them and
they all pass. I may add them to libc-testsuite soon; the only reason
I haven't done so yet is that I'd want a way to selectively disable
some that won't be supported on all systems, and as of yet
libc-testsuite does not have a good framework for making some tests
optional.
I've also made crypt_r public through crypt.h.
Feedback is welcome. If anyone's interested in helping get md5, sha,
or other hash types integrated (while keeping the size cost down) that
would be great too.
Rich
^ permalink raw reply [flat|nested] 17+ messages in thread
end of thread, other threads:[~2012-06-29 5:25 UTC | newest]
Thread overview: 17+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2012-06-12 23:51 FreeSec crypt() Solar Designer
2012-06-13 1:18 ` Rich Felker
2012-06-13 6:10 ` Szabolcs Nagy
2012-06-13 12:43 ` Solar Designer
2012-06-13 12:58 ` Rich Felker
2012-06-13 13:18 ` Solar Designer
2012-06-13 14:56 ` Rich Felker
2012-06-13 16:45 ` Solar Designer
2012-06-13 17:27 ` Rich Felker
2012-06-13 17:32 ` Szabolcs Nagy
2012-06-13 17:36 ` Rich Felker
2012-06-13 12:07 ` Solar Designer
2012-06-13 14:53 ` Rich Felker
2012-06-24 7:21 ` Solar Designer
2012-06-24 7:32 ` Solar Designer
2012-06-25 3:51 ` Rich Felker
2012-06-29 5:25 ` Rich Felker
Code repositories for project(s) associated with this public inbox
https://git.vuxu.org/mirror/musl/
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).