crypt(3)

helios (17607)
So I found a C implementation of crypt(3) (http://en.wikipedia.org/wiki/Crypt_%28Unix%29#Library_Function ), but I'm having some trouble getting it to work. It's weird. With MinGW and GCC 4.x it produces the correct output, but with GCC 3.x and VC++, it doesn't. The kind of output it gives me makes me suspect of uninitialized data, but I passed it through Valgrind and got nothing (then again, I did pass a version that gave correct results). Compiling as C code doesn't help.
Any idea of what could be causing it? Alternative implementations are also welcome.

This is the implementation I used:
http://google.com/codesearch/p#miRTe8ZyR0o/Archive/PDP-11/Distributions/research/Henry_Spencer_v7/v7.tar.gz|118goTAkg2o/usr/src/libc/gen/crypt.c
Last edited on
PanGalactic (1658)
Wow. What a fossil. How the hell does that even compile on modern compilers? Ancient K&R syntax, including missing argument declarations, missing return types, register variables, etc.

Check out the version in GNU glibc: ftp://ftp.win.tue.nl/pub/home/aeb/linux-local/libc.archive/glibc/glibc-crypt-2.1.tar.gz
helios (17607)
How the hell does that even compile on modern compilers?
Obviously, I touched up the function signatures and variable declarations a bit.

The link gives me a 550, but I'll try getting the glibc source elsewhere.
helios (17607)
Well, glibc's crypt() was so long, I figured it would be easier to fix the one above. I think I found the problem. The code is relying heavily on undefined behavior.
For example, I just found this:
1
2
3
4
5
6
7
 
static char L[32],R[32];
//...
//(in a function)
int i;
//...
for (i=0;i<64;i++)
    L[i]=/*...*/;

When I moved the arrays to local storage, the for became an infinite loop because I declared i before L, so overflowing the buffer was overwriting i with a zero.
helios (17607)
Friggin' finally!
The code relied on undefined behavior at two locations. Is it so much to ask from a C programmer to not make assumptions about the relative physical positions of arrays?

I'll leave the working version here in case anyone needs it. It should be valid C, I think. I changed the interface a bit because I wanted to make it thread-safe, and returning a pointer to a static array is a no-no.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
 
#ifdef __cplusplus
#include <cstring>

#define NAMESPACE_MY_OPEN namespace my{
#define NAMESPACE_MY_CLOSE }
#else
#include <string.h>

#define NAMESPACE_MY_OPEN
#define NAMESPACE_MY_CLOSE
#endif

NAMESPACE_MY_OPEN

static char IP[]={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},
	FP[]={40,8,48,16,56,24,64,32,39,7,47,15,55,23,63,31,38,6,46,14,54,22,62,30,37,5,45,13,53,21,61,29,36,4,44,12,52,20,60,28,35,3,43,11,51,19,59,27,34,2,42,10,50,18,58,26,33,1,41,9,49,17,57,25},
	PC1_C[]={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},
	PC1_D[]={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},
	shifts[]={1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1},
	PC2_C[]={14,17,11,24,1,5,3,28,15,6,21,10,23,19,12,4,26,8,16,7,27,20,13,2},
	PC2_D[]={41,52,31,37,47,55,30,40,51,45,33,48,44,49,39,56,34,53,46,42,50,36,29,32},
	e[]={32,1,2,3,4,5,4,5,6,7,8,9,8,9,10,11,12,13,12,13,14,15,16,17,16,17,18,19,20,21,20,21,22,23,24,25,24,25,26,27,28,29,28,29,30,31,32,1},
	S[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}
	},
	P[]={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};


void setkey(char *key,char C[28],char D[28],char KS[16][48]){
	int i=0,
		j=0,
		k=0,
		t=0;
	for (i=0;i<28;i++){
		C[i]=key[PC1_C[i]-1];
		D[i]=key[PC1_D[i]-1];
	}
	for (i=0;i<16;i++) {
		for (k=0;k<shifts[i];k++){
			t=C[0];
			for (j=0;j<28-1;j++)
				C[j]=C[j+1];
			C[27]=t;
			t=D[0];
			for (j=0;j<28-1;j++)
				D[j]=D[j+1];
			D[27]=t;
		}
		for (j=0;j<24;j++) {
			KS[i][j]=C[PC2_C[j]-1];
			KS[i][j+24]=D[PC2_D[j]-28-1];
		}
	}
}

void encrypt(char *block,int edflag,char KS[16][48],char E[48]){
	int i=0,
		ii=0,
		j=0,
		k=0;
	char L[32],
		R[32],
		tempL[32],
		f[32],
		preS[48];

	for (j=0;j<32;j++){
		L[j]=block[IP[j]-1];
		R[j]=block[IP[j+32]-1];
	}

	for (ii=0;ii<16;ii++) {
		if (edflag)
			i=15-ii;
		else
			i=ii;
		memcpy(tempL,R,32);
		for (j=0;j<48;j++)
			preS[j]=R[E[j]-1]^KS[i][j];
		for (j=0;j<8;j++) {
			char t;
			t=6*j;
			k=S[j][(preS[t+0]<<5)+(preS[t+1]<<3)+(preS[t+2]<<2)+(preS[t+3]<<1)+(preS[t+4]<<0)+(preS[t+5]<<4)];
			t=4*j;
			f[t+0]=(k>>3)&1;
			f[t+1]=(k>>2)&1;
			f[t+2]=(k>>1)&1;
			f[t+3]=(k>>0)&1;
		}
		for (j=0;j<32;j++)
			R[j]=L[j]^f[P[j]-1];
		memcpy(L,tempL,32);
	}
	for (j=0;j<32;j++){
		char t;
		t=L[j];
		L[j]=R[j];
		R[j]=t;
	}
	for (j=0;j<32;j++){
		char a;
		a=FP[j]-1;
		block[j   ]=((a<32)?L:R)[a%32];
		a=FP[j+32]-1;
		block[j+32]=((a<32)?L:R)[a%32];
	}
}

void crypt(char dst[16],const char *pw,const char *salt){
	int i=0,
		j=0,
		c=0,
		temp=0;
	char block[66],
		C[28],
		D[28],
		KS[16][48],
		E[48];

	memset(block,0,66);
	for(i=0;(c=*pw) && i<64;pw++){
		for(j=0;j<7;j++,i++)
			block[i]=(c>>(6-j))&1;
		i++;
	}

	setkey(block,C,D,KS);
	memset(block,0,66);
	memcpy(E,e,48);

	for(i=0;i<2;i++){
		c=*salt++;
		dst[i]=c;
		if(c>'Z')
			c-=6;
		if(c>'9')
			c-=7;
		c-='.';
		for (j=0;j<6;j++){
			if((c>>j)&1){
				temp=E[6*i+j];
				E[6*i+j]=E[6*i+j+24];
				E[6*i+j+24]=temp;
			}
		}
	}

	for(i=0; i<25; i++)
		encrypt(block,0,KS,E);

	for(i=0;i<11;i++){
		c=0;
		for(j=0;j<6;j++){
			c<<=1;
			c|=block[6*i+j];
		}
		c+='.';
		if(c>'9')
			c += 7;
		if(c>'Z')
			c += 6;
		dst[i+2]=c;
	}
	dst[i+2]=0;
	if(dst[1]==0)
		dst[1]=dst[0];
}

NAMESPACE_MY_CLOSE


EDIT: Okay, now it's definitely valid (gcc file.c -pedantic -std=c89).
Last edited on
chrisname (7395)
Valid C, but with a namespace? What?

namespace my{
Should be
1
2
3
 
#ifdef __cplusplus
namespace my{
#endif

if you want it to compile with a C compiler :)
Last edited on
helios (17607)
Oops.
chrisname (7395)
I surmised as much ;)
Topic archived. No new replies allowed.