-
Notifications
You must be signed in to change notification settings - Fork 0
/
SHA-crypt.txt
1867 lines (1551 loc) · 60.1 KB
/
SHA-crypt.txt
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
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
Unix crypt using SHA-256 and SHA-512
------------------------------------
Author: Ulrich Drepper <[email protected]>
Version: 0.4 2008-4-3
Discussion Group:
Josh Bressers, Red Hat
Mark Brown, IBM
David Clissold, IBM
Don Cragun, Sun
Casper Dik, Sun
Ulrich Drepper, Red Hat
Larry Dwyer, HP
Steve Grubb, Red Hat
Ravi A Shankar, IBM
Borislav Simov, HP
Various Unix crypt implementations have been MD5 as an alternative
method to the traditional DES encryption for the one-way conversion
needed. Both DES and MD5 are deemed insecure for their primary
purpose and by association their use in password encryption is put
into question. In addition, the produced output for both DES and MD5
has a short length which makes it possible to construct rainbow tables.
Requests for a better solution to the problem have been heard for some
time. Security departments in companies are trying to phase out all
uses of MD5. They demand a method which is officially sanctioned.
For US-based users this means tested by the NIST.
This rules out the use of another already implemented method with
limited spread: the use of the Blowfish encryption method. The choice
comes down to tested encryption (3DES, AES) or hash sums (the SHA
family).
Encryption-based solution do not seem to provide better security (no
proof to the contrary) and the higher CPU requirements can be
compensated for by adding more complexity to a hash sum-based
solution. This is why the decision has been made by a group of Unix
and Linux vendors to persue this route.
The SHA hash sum functions are well tested. By choosing the SHA-256
and SHA-512 algorithms the produced output is 32 or 64 bytes
respectively in size. This fulfills the requirement for a large
output set which makes rainbow tables less useful to impossible, at
least for the next years.
The algorithm used by the MD5-based password hashing is generally
deemed safe as well so there is no big problem with using a similar
algorithm for the SHA-based password hashing solutions. Parts of the
algorithm have been changed and in one instance what is thought to be
a mistake in the MD5-based implementation has been fixed.
The integration into existing systems is easy if those systems already
support the MD5-based solution. Ever since the introduction of the
MD5-based method an extended password format is in used:
$<ID>$<SALT>$<PWD>
If the password is not of this form it is an old-style DES-encrypted
password. If the password has this form the ID identifies the method
used and this then determines how the rest of the password string is
interpreted. So far the following ID values are in use:
ID | Method
-------------------------------
1 | MD5 (Linux, BSD)
2a | Blowfish (OpenBSD)
md5 | Sun MD5
For the new SHA-256 and SHA-512 methods the following values are
selected:
ID | Method
-------------------------------
5 | SHA-256
6 | SHA-512
For the SHA-based methods the SALT string can be a simple string of
which up to 16 characters are used. The MD5-based implementation used
up to eight characters.. It was decided to allow one extension which
follows an invention Sun implemented in their pluggable crypt
implementation. If the SALT strings starts with
rounds=<N>$
where N is an unsigned decimal number the numeric value of N is used
to modify the algorithm used. As will be explained later, the
SHA-based algorithm contains a loop which can be run an arbitrary
number of times. The more rounds are performed the higher the CPU
requirements are. This is a safety mechanism which might help
countering brute-force attacks in the face of increasing computing
power.
The default number of rounds for both algorithms is 5000. To ensure
minimal security and stability on the other hand minimum and maximum
values for N are enforced:
minimum for N = 1,000
maximum for N = 999,999,999
Any selection of N below the minimum will cause the use of 1,000
rounds and a value of 1 billion and higher will cause 999,999,999
rounds to be used. In these cases the output string produced by the
crypt function will not have the same salt as the input salt string
since the correct, limited rounds value is used in the output.
The PWD part of the password string is the actual computed password.
The size of this string is fixed:
SHA-256 43 characters
SHA-512 86 characters
The output consists of the base64-encoded digest. The maximum length
of a password string is therefore (excluding final NUL byte in the C
representation):
SHA-256 80 characters
SHA-512 123 characters
The input string used for the salt parameter of the crypt function can
potentially be much longer. But since the salt string is truncated to
at most 16 characters the size of the output string is limited.
The algorithm used for the password hashing follows the one used in
the Linux/BSD MD5 implementation. The following is a description of
the algorithm where the differences are explicitly pointed out. Both,
the SHA-256 and the SHA-512 method, use the same algorithm. The only
difference, which is also a difference to the MD5 version, are all the
cases where an existing digest is used as input for another digest
computation. In this case the input size (i.e., the digest size)
varies. For MD5 the digest is 16 bytes, for SHA-256 it is 32 bytes,
and for SHA-512 it is 64 bytes. The following description will not
mention this difference further.
The algorithm using three primitives for creating a hash digest:
- start a digest. This sets up the data structures and initial state
as required for the hash function
- add bytes to a digest. This can happen multiple times. Only when
the required number of bytes for a round of the hash function is
added will anything happen. If the required number of bytes is not
yet reached the bytes will simply be queued up. For SHA-256 and
SHA-512 the respective sizes are 64 and 128 bytes.
- finish the context. This operation causes the currently queued
bytes to be padded according to the hash function specification and
the result is processed. The final digest is computed and made
available to the use.
When the algorithm talks about adding the salt string this really
means adding the salt string truncated to 16 characters.
When the algorithm talks about adding a string the terminating NUL
byte of the C presentation of the string in NOT added.
Algorithm for crypt using SHA-256/SHA-512:
1. start digest A
2. the password string is added to digest A
3. the salt string is added to digest A. This is just the salt string
itself without the enclosing '$', without the magic prefix $5$ and
$6$ respectively and without the rounds=<N> specification.
NB: the MD5 algorithm did add the $1$ prefix. This is not deemed
necessary since it is a constant string and does not add security
and /possibly/ allows a plain text attack. Since the rounds=<N>
specification should never be added this would also create an
inconsistency.
4. start digest B
5. add the password to digest B
6. add the salt string to digest B
7. add the password again to digest B
8. finish digest B
9. For each block of 32 or 64 bytes in the password string (excluding
the terminating NUL in the C representation), add digest B to digest A
10. For the remaining N bytes of the password string add the first
N bytes of digest B to digest A
11. For each bit of the binary representation of the length of the
password string up to and including the highest 1-digit, starting
from to lowest bit position (numeric value 1):
a) for a 1-digit add digest B to digest A
b) for a 0-digit add the password string
NB: this step differs significantly from the MD5 algorithm. It
adds more randomness.
12. finish digest A
13. start digest DP
14. for every byte in the password (excluding the terminating NUL byte
in the C representation of the string)
add the password to digest DP
15. finish digest DP
16. produce byte sequence P of the same length as the password where
a) for each block of 32 or 64 bytes of length of the password string
the entire digest DP is used
b) for the remaining N (up to 31 or 63) bytes use the first N
bytes of digest DP
17. start digest DS
18. repeast the following 16+A[0] times, where A[0] represents the first
byte in digest A interpreted as an 8-bit unsigned value
add the salt to digest DS
19. finish digest DS
20. produce byte sequence S of the same length as the salt string where
a) for each block of 32 or 64 bytes of length of the salt string
the entire digest DS is used
b) for the remaining N (up to 31 or 63) bytes use the first N
bytes of digest DS
21. repeat a loop according to the number specified in the rounds=<N>
specification in the salt (or the default value if none is
present). Each round is numbered, starting with 0 and up to N-1.
The loop uses a digest as input. In the first round it is the
digest produced in step 12. In the latter steps it is the digest
produced in step 21.h. The following text uses the notation
"digest A/C" to describe this behavior.
a) start digest C
b) for odd round numbers add the byte sequense P to digest C
c) for even round numbers add digest A/C
d) for all round numbers not divisible by 3 add the byte sequence S
e) for all round numbers not divisible by 7 add the byte sequence P
f) for odd round numbers add digest A/C
g) for even round numbers add the byte sequence P
h) finish digest C.
22. Produce the output string. This is an ASCII string of the maximum
size specified above, consisting of multiple pieces:
a) the salt prefix, $5$ or $6$ respectively
b) the rounds=<N> specification, if one was present in the input
salt string. A trailing '$' is added in this case to separate
the rounds specification from the following text.
c) the salt string truncated to 16 characters
d) a '$' character
e) the base-64 encoded final C digest. The encoding used is as
follows:
111111111122222222223333333333444444444455555555556666
0123456789012345678901234567890123456789012345678901234567890123
----------------------------------------------------------------
./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
Each group of three bytes from the digest produces four
characters as output:
1. character: the six low bits of the first byte
2. character: the two high bits of the first byte and the
four low bytes from the second byte
3. character: the four high butes from the second byte and
the two low bits from the third byte
4. character: the six high bits from the third byte
The groups of three bytes are as follows (in this sequence).
These are the indices into the byte array containing the
digest, starting with index 0. For the last group there are
not enough bytes left in the digest and the value zero is used
in its place. This group also produces only three or two
characters as output for SHA-256 and SHA-512 respecitevely.
For SHA-256:
#3 #2 #1 <-- byte number in group
0 - 10 - 20
21 - 1 - 11
12 - 22 - 2
3 - 13 - 23
24 - 4 - 14
15 - 25 - 5
6 - 16 - 26
27 - 7 - 17
18 - 28 - 8
9 - 19 - 29
* - 31 - 30
For SHA-512:
#3 #2 #1 <-- byte number in group
0 - 21 - 42
22 - 43 - 1
44 - 2 - 23
3 - 24 - 45
25 - 46 - 4
47 - 5 - 26
6 - 27 - 48
28 - 49 - 7
50 - 8 - 29
9 - 30 - 51
31 - 52 - 10
53 - 11 - 32
12 - 33 - 54
34 - 55 - 13
56 - 14 - 35
15 - 36 - 57
37 - 58 - 16
59 - 17 - 38
18 - 39 - 60
40 - 61 - 19
62 - 20 - 41
* - * - 63
The following are complete implementation of the crypt variants using
SHA-256 and SHA-512 respectively. The sources include a self test
which can be enabled by defining the macro TEST.
-------- sha256crypt.c ------------------------------------------------------
/* SHA256-based Unix crypt implementation.
Released into the Public Domain by Ulrich Drepper <[email protected]>. */
#include <endian.h>
#include <errno.h>
#include <limits.h>
#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/param.h>
#include <sys/types.h>
/* Structure to save state of computation between the single steps. */
struct sha256_ctx
{
uint32_t H[8];
uint32_t total[2];
uint32_t buflen;
char buffer[128]; /* NB: always correctly aligned for uint32_t. */
};
#if __BYTE_ORDER == __LITTLE_ENDIAN
# define SWAP(n) \
(((n) << 24) | (((n) & 0xff00) << 8) | (((n) >> 8) & 0xff00) | ((n) >> 24))
#else
# define SWAP(n) (n)
#endif
/* This array contains the bytes used to pad the buffer to the next
64-byte boundary. (FIPS 180-2:5.1.1) */
static const unsigned char fillbuf[64] = { 0x80, 0 /* , 0, 0, ... */ };
/* Constants for SHA256 from FIPS 180-2:4.2.2. */
static const uint32_t K[64] =
{
0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5,
0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3,
0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc,
0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7,
0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13,
0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3,
0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5,
0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,
0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
};
/* Process LEN bytes of BUFFER, accumulating context into CTX.
It is assumed that LEN % 64 == 0. */
static void
sha256_process_block (const void *buffer, size_t len, struct sha256_ctx *ctx)
{
const uint32_t *words = buffer;
size_t nwords = len / sizeof (uint32_t);
uint32_t a = ctx->H[0];
uint32_t b = ctx->H[1];
uint32_t c = ctx->H[2];
uint32_t d = ctx->H[3];
uint32_t e = ctx->H[4];
uint32_t f = ctx->H[5];
uint32_t g = ctx->H[6];
uint32_t h = ctx->H[7];
/* First increment the byte count. FIPS 180-2 specifies the possible
length of the file up to 2^64 bits. Here we only compute the
number of bytes. Do a double word increment. */
ctx->total[0] += len;
if (ctx->total[0] < len)
++ctx->total[1];
/* Process all bytes in the buffer with 64 bytes in each round of
the loop. */
while (nwords > 0)
{
uint32_t W[64];
uint32_t a_save = a;
uint32_t b_save = b;
uint32_t c_save = c;
uint32_t d_save = d;
uint32_t e_save = e;
uint32_t f_save = f;
uint32_t g_save = g;
uint32_t h_save = h;
/* Operators defined in FIPS 180-2:4.1.2. */
#define Ch(x, y, z) ((x & y) ^ (~x & z))
#define Maj(x, y, z) ((x & y) ^ (x & z) ^ (y & z))
#define S0(x) (CYCLIC (x, 2) ^ CYCLIC (x, 13) ^ CYCLIC (x, 22))
#define S1(x) (CYCLIC (x, 6) ^ CYCLIC (x, 11) ^ CYCLIC (x, 25))
#define R0(x) (CYCLIC (x, 7) ^ CYCLIC (x, 18) ^ (x >> 3))
#define R1(x) (CYCLIC (x, 17) ^ CYCLIC (x, 19) ^ (x >> 10))
/* It is unfortunate that C does not provide an operator for
cyclic rotation. Hope the C compiler is smart enough. */
#define CYCLIC(w, s) ((w >> s) | (w << (32 - s)))
/* Compute the message schedule according to FIPS 180-2:6.2.2 step 2. */
for (unsigned int t = 0; t < 16; ++t)
{
W[t] = SWAP (*words);
++words;
}
for (unsigned int t = 16; t < 64; ++t)
W[t] = R1 (W[t - 2]) + W[t - 7] + R0 (W[t - 15]) + W[t - 16];
/* The actual computation according to FIPS 180-2:6.2.2 step 3. */
for (unsigned int t = 0; t < 64; ++t)
{
uint32_t T1 = h + S1 (e) + Ch (e, f, g) + K[t] + W[t];
uint32_t T2 = S0 (a) + Maj (a, b, c);
h = g;
g = f;
f = e;
e = d + T1;
d = c;
c = b;
b = a;
a = T1 + T2;
}
/* Add the starting values of the context according to FIPS 180-2:6.2.2
step 4. */
a += a_save;
b += b_save;
c += c_save;
d += d_save;
e += e_save;
f += f_save;
g += g_save;
h += h_save;
/* Prepare for the next round. */
nwords -= 16;
}
/* Put checksum in context given as argument. */
ctx->H[0] = a;
ctx->H[1] = b;
ctx->H[2] = c;
ctx->H[3] = d;
ctx->H[4] = e;
ctx->H[5] = f;
ctx->H[6] = g;
ctx->H[7] = h;
}
/* Initialize structure containing state of computation.
(FIPS 180-2:5.3.2) */
static void
sha256_init_ctx (struct sha256_ctx *ctx)
{
ctx->H[0] = 0x6a09e667;
ctx->H[1] = 0xbb67ae85;
ctx->H[2] = 0x3c6ef372;
ctx->H[3] = 0xa54ff53a;
ctx->H[4] = 0x510e527f;
ctx->H[5] = 0x9b05688c;
ctx->H[6] = 0x1f83d9ab;
ctx->H[7] = 0x5be0cd19;
ctx->total[0] = ctx->total[1] = 0;
ctx->buflen = 0;
}
/* Process the remaining bytes in the internal buffer and the usual
prolog according to the standard and write the result to RESBUF.
IMPORTANT: On some systems it is required that RESBUF is correctly
aligned for a 32 bits value. */
static void *
sha256_finish_ctx (struct sha256_ctx *ctx, void *resbuf)
{
/* Take yet unprocessed bytes into account. */
uint32_t bytes = ctx->buflen;
size_t pad;
/* Now count remaining bytes. */
ctx->total[0] += bytes;
if (ctx->total[0] < bytes)
++ctx->total[1];
pad = bytes >= 56 ? 64 + 56 - bytes : 56 - bytes;
memcpy (&ctx->buffer[bytes], fillbuf, pad);
/* Put the 64-bit file length in *bits* at the end of the buffer. */
*(uint32_t *) &ctx->buffer[bytes + pad + 4] = SWAP (ctx->total[0] << 3);
*(uint32_t *) &ctx->buffer[bytes + pad] = SWAP ((ctx->total[1] << 3) |
(ctx->total[0] >> 29));
/* Process last bytes. */
sha256_process_block (ctx->buffer, bytes + pad + 8, ctx);
/* Put result from CTX in first 32 bytes following RESBUF. */
for (unsigned int i = 0; i < 8; ++i)
((uint32_t *) resbuf)[i] = SWAP (ctx->H[i]);
return resbuf;
}
static void
sha256_process_bytes (const void *buffer, size_t len, struct sha256_ctx *ctx)
{
/* When we already have some bits in our internal buffer concatenate
both inputs first. */
if (ctx->buflen != 0)
{
size_t left_over = ctx->buflen;
size_t add = 128 - left_over > len ? len : 128 - left_over;
memcpy (&ctx->buffer[left_over], buffer, add);
ctx->buflen += add;
if (ctx->buflen > 64)
{
sha256_process_block (ctx->buffer, ctx->buflen & ~63, ctx);
ctx->buflen &= 63;
/* The regions in the following copy operation cannot overlap. */
memcpy (ctx->buffer, &ctx->buffer[(left_over + add) & ~63],
ctx->buflen);
}
buffer = (const char *) buffer + add;
len -= add;
}
/* Process available complete blocks. */
if (len >= 64)
{
/* To check alignment gcc has an appropriate operator. Other
compilers don't. */
#if __GNUC__ >= 2
# define UNALIGNED_P(p) (((uintptr_t) p) % __alignof__ (uint32_t) != 0)
#else
# define UNALIGNED_P(p) (((uintptr_t) p) % sizeof (uint32_t) != 0)
#endif
if (UNALIGNED_P (buffer))
while (len > 64)
{
sha256_process_block (memcpy (ctx->buffer, buffer, 64), 64, ctx);
buffer = (const char *) buffer + 64;
len -= 64;
}
else
{
sha256_process_block (buffer, len & ~63, ctx);
buffer = (const char *) buffer + (len & ~63);
len &= 63;
}
}
/* Move remaining bytes into internal buffer. */
if (len > 0)
{
size_t left_over = ctx->buflen;
memcpy (&ctx->buffer[left_over], buffer, len);
left_over += len;
if (left_over >= 64)
{
sha256_process_block (ctx->buffer, 64, ctx);
left_over -= 64;
memcpy (ctx->buffer, &ctx->buffer[64], left_over);
}
ctx->buflen = left_over;
}
}
/* Define our magic string to mark salt for SHA256 "encryption"
replacement. */
static const char sha256_salt_prefix[] = "$5$";
/* Prefix for optional rounds specification. */
static const char sha256_rounds_prefix[] = "rounds=";
/* Maximum salt string length. */
#define SALT_LEN_MAX 16
/* Default number of rounds if not explicitly specified. */
#define ROUNDS_DEFAULT 5000
/* Minimum number of rounds. */
#define ROUNDS_MIN 1000
/* Maximum number of rounds. */
#define ROUNDS_MAX 999999999
/* Table with characters for base64 transformation. */
static const char b64t[64] =
"./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
static char *
sha256_crypt_r (const char *key, const char *salt, char *buffer, int buflen)
{
unsigned char alt_result[32]
__attribute__ ((__aligned__ (__alignof__ (uint32_t))));
unsigned char temp_result[32]
__attribute__ ((__aligned__ (__alignof__ (uint32_t))));
struct sha256_ctx ctx;
struct sha256_ctx alt_ctx;
size_t salt_len;
size_t key_len;
size_t cnt;
char *cp;
char *copied_key = NULL;
char *copied_salt = NULL;
char *p_bytes;
char *s_bytes;
/* Default number of rounds. */
size_t rounds = ROUNDS_DEFAULT;
bool rounds_custom = false;
/* Find beginning of salt string. The prefix should normally always
be present. Just in case it is not. */
if (strncmp (sha256_salt_prefix, salt, sizeof (sha256_salt_prefix) - 1) == 0)
/* Skip salt prefix. */
salt += sizeof (sha256_salt_prefix) - 1;
if (strncmp (salt, sha256_rounds_prefix, sizeof (sha256_rounds_prefix) - 1)
== 0)
{
const char *num = salt + sizeof (sha256_rounds_prefix) - 1;
char *endp;
unsigned long int srounds = strtoul (num, &endp, 10);
if (*endp == '$')
{
salt = endp + 1;
rounds = MAX (ROUNDS_MIN, MIN (srounds, ROUNDS_MAX));
rounds_custom = true;
}
}
salt_len = MIN (strcspn (salt, "$"), SALT_LEN_MAX);
key_len = strlen (key);
if ((key - (char *) 0) % __alignof__ (uint32_t) != 0)
{
char *tmp = (char *) alloca (key_len + __alignof__ (uint32_t));
key = copied_key =
memcpy (tmp + __alignof__ (uint32_t)
- (tmp - (char *) 0) % __alignof__ (uint32_t),
key, key_len);
}
if ((salt - (char *) 0) % __alignof__ (uint32_t) != 0)
{
char *tmp = (char *) alloca (salt_len + __alignof__ (uint32_t));
salt = copied_salt =
memcpy (tmp + __alignof__ (uint32_t)
- (tmp - (char *) 0) % __alignof__ (uint32_t),
salt, salt_len);
}
/* Prepare for the real work. */
sha256_init_ctx (&ctx);
/* Add the key string. */
sha256_process_bytes (key, key_len, &ctx);
/* The last part is the salt string. This must be at most 16
characters and it ends at the first `$' character (for
compatibility with existing implementations). */
sha256_process_bytes (salt, salt_len, &ctx);
/* Compute alternate SHA256 sum with input KEY, SALT, and KEY. The
final result will be added to the first context. */
sha256_init_ctx (&alt_ctx);
/* Add key. */
sha256_process_bytes (key, key_len, &alt_ctx);
/* Add salt. */
sha256_process_bytes (salt, salt_len, &alt_ctx);
/* Add key again. */
sha256_process_bytes (key, key_len, &alt_ctx);
/* Now get result of this (32 bytes) and add it to the other
context. */
sha256_finish_ctx (&alt_ctx, alt_result);
/* Add for any character in the key one byte of the alternate sum. */
for (cnt = key_len; cnt > 32; cnt -= 32)
sha256_process_bytes (alt_result, 32, &ctx);
sha256_process_bytes (alt_result, cnt, &ctx);
/* Take the binary representation of the length of the key and for every
1 add the alternate sum, for every 0 the key. */
for (cnt = key_len; cnt > 0; cnt >>= 1)
if ((cnt & 1) != 0)
sha256_process_bytes (alt_result, 32, &ctx);
else
sha256_process_bytes (key, key_len, &ctx);
/* Create intermediate result. */
sha256_finish_ctx (&ctx, alt_result);
/* Start computation of P byte sequence. */
sha256_init_ctx (&alt_ctx);
/* For every character in the password add the entire password. */
for (cnt = 0; cnt < key_len; ++cnt)
sha256_process_bytes (key, key_len, &alt_ctx);
/* Finish the digest. */
sha256_finish_ctx (&alt_ctx, temp_result);
/* Create byte sequence P. */
cp = p_bytes = alloca (key_len);
for (cnt = key_len; cnt >= 32; cnt -= 32)
cp = mempcpy (cp, temp_result, 32);
memcpy (cp, temp_result, cnt);
/* Start computation of S byte sequence. */
sha256_init_ctx (&alt_ctx);
/* For every character in the password add the entire password. */
for (cnt = 0; cnt < 16 + alt_result[0]; ++cnt)
sha256_process_bytes (salt, salt_len, &alt_ctx);
/* Finish the digest. */
sha256_finish_ctx (&alt_ctx, temp_result);
/* Create byte sequence S. */
cp = s_bytes = alloca (salt_len);
for (cnt = salt_len; cnt >= 32; cnt -= 32)
cp = mempcpy (cp, temp_result, 32);
memcpy (cp, temp_result, cnt);
/* Repeatedly run the collected hash value through SHA256 to burn
CPU cycles. */
for (cnt = 0; cnt < rounds; ++cnt)
{
/* New context. */
sha256_init_ctx (&ctx);
/* Add key or last result. */
if ((cnt & 1) != 0)
sha256_process_bytes (p_bytes, key_len, &ctx);
else
sha256_process_bytes (alt_result, 32, &ctx);
/* Add salt for numbers not divisible by 3. */
if (cnt % 3 != 0)
sha256_process_bytes (s_bytes, salt_len, &ctx);
/* Add key for numbers not divisible by 7. */
if (cnt % 7 != 0)
sha256_process_bytes (p_bytes, key_len, &ctx);
/* Add key or last result. */
if ((cnt & 1) != 0)
sha256_process_bytes (alt_result, 32, &ctx);
else
sha256_process_bytes (p_bytes, key_len, &ctx);
/* Create intermediate result. */
sha256_finish_ctx (&ctx, alt_result);
}
/* Now we can construct the result string. It consists of three
parts. */
cp = stpncpy (buffer, sha256_salt_prefix, MAX (0, buflen));
buflen -= sizeof (sha256_salt_prefix) - 1;
if (rounds_custom)
{
int n = snprintf (cp, MAX (0, buflen), "%s%zu$",
sha256_rounds_prefix, rounds);
cp += n;
buflen -= n;
}
cp = stpncpy (cp, salt, MIN ((size_t) MAX (0, buflen), salt_len));
buflen -= MIN ((size_t) MAX (0, buflen), salt_len);
if (buflen > 0)
{
*cp++ = '$';
--buflen;
}
#define b64_from_24bit(B2, B1, B0, N) \
do { \
unsigned int w = ((B2) << 16) | ((B1) << 8) | (B0); \
int n = (N); \
while (n-- > 0 && buflen > 0) \
{ \
*cp++ = b64t[w & 0x3f]; \
--buflen; \
w >>= 6; \
} \
} while (0)
b64_from_24bit (alt_result[0], alt_result[10], alt_result[20], 4);
b64_from_24bit (alt_result[21], alt_result[1], alt_result[11], 4);
b64_from_24bit (alt_result[12], alt_result[22], alt_result[2], 4);
b64_from_24bit (alt_result[3], alt_result[13], alt_result[23], 4);
b64_from_24bit (alt_result[24], alt_result[4], alt_result[14], 4);
b64_from_24bit (alt_result[15], alt_result[25], alt_result[5], 4);
b64_from_24bit (alt_result[6], alt_result[16], alt_result[26], 4);
b64_from_24bit (alt_result[27], alt_result[7], alt_result[17], 4);
b64_from_24bit (alt_result[18], alt_result[28], alt_result[8], 4);
b64_from_24bit (alt_result[9], alt_result[19], alt_result[29], 4);
b64_from_24bit (0, alt_result[31], alt_result[30], 3);
if (buflen <= 0)
{
errno = ERANGE;
buffer = NULL;
}
else
*cp = '\0'; /* Terminate the string. */
/* Clear the buffer for the intermediate result so that people
attaching to processes or reading core dumps cannot get any
information. We do it in this way to clear correct_words[]
inside the SHA256 implementation as well. */
sha256_init_ctx (&ctx);
sha256_finish_ctx (&ctx, alt_result);
memset (temp_result, '\0', sizeof (temp_result));
memset (p_bytes, '\0', key_len);
memset (s_bytes, '\0', salt_len);
memset (&ctx, '\0', sizeof (ctx));
memset (&alt_ctx, '\0', sizeof (alt_ctx));
if (copied_key != NULL)
memset (copied_key, '\0', key_len);
if (copied_salt != NULL)
memset (copied_salt, '\0', salt_len);
return buffer;
}
/* This entry point is equivalent to the `crypt' function in Unix
libcs. */
char *
sha256_crypt (const char *key, const char *salt)
{
/* We don't want to have an arbitrary limit in the size of the
password. We can compute an upper bound for the size of the
result in advance and so we can prepare the buffer we pass to
`sha256_crypt_r'. */
static char *buffer;
static int buflen;
int needed = (sizeof (sha256_salt_prefix) - 1
+ sizeof (sha256_rounds_prefix) + 9 + 1
+ strlen (salt) + 1 + 43 + 1);
if (buflen < needed)
{
char *new_buffer = (char *) realloc (buffer, needed);
if (new_buffer == NULL)
return NULL;
buffer = new_buffer;
buflen = needed;
}
return sha256_crypt_r (key, salt, buffer, buflen);
}
#ifdef TEST
static const struct
{
const char *input;
const char result[32];
} tests[] =
{
/* Test vectors from FIPS 180-2: appendix B.1. */
{ "abc",
"\xba\x78\x16\xbf\x8f\x01\xcf\xea\x41\x41\x40\xde\x5d\xae\x22\x23"
"\xb0\x03\x61\xa3\x96\x17\x7a\x9c\xb4\x10\xff\x61\xf2\x00\x15\xad" },
/* Test vectors from FIPS 180-2: appendix B.2. */
{ "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq",
"\x24\x8d\x6a\x61\xd2\x06\x38\xb8\xe5\xc0\x26\x93\x0c\x3e\x60\x39"
"\xa3\x3c\xe4\x59\x64\xff\x21\x67\xf6\xec\xed\xd4\x19\xdb\x06\xc1" },
/* Test vectors from the NESSIE project. */
{ "",
"\xe3\xb0\xc4\x42\x98\xfc\x1c\x14\x9a\xfb\xf4\xc8\x99\x6f\xb9\x24"
"\x27\xae\x41\xe4\x64\x9b\x93\x4c\xa4\x95\x99\x1b\x78\x52\xb8\x55" },
{ "a",
"\xca\x97\x81\x12\xca\x1b\xbd\xca\xfa\xc2\x31\xb3\x9a\x23\xdc\x4d"
"\xa7\x86\xef\xf8\x14\x7c\x4e\x72\xb9\x80\x77\x85\xaf\xee\x48\xbb" },
{ "message digest",
"\xf7\x84\x6f\x55\xcf\x23\xe1\x4e\xeb\xea\xb5\xb4\xe1\x55\x0c\xad"
"\x5b\x50\x9e\x33\x48\xfb\xc4\xef\xa3\xa1\x41\x3d\x39\x3c\xb6\x50" },
{ "abcdefghijklmnopqrstuvwxyz",
"\x71\xc4\x80\xdf\x93\xd6\xae\x2f\x1e\xfa\xd1\x44\x7c\x66\xc9\x52"
"\x5e\x31\x62\x18\xcf\x51\xfc\x8d\x9e\xd8\x32\xf2\xda\xf1\x8b\x73" },
{ "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq",
"\x24\x8d\x6a\x61\xd2\x06\x38\xb8\xe5\xc0\x26\x93\x0c\x3e\x60\x39"
"\xa3\x3c\xe4\x59\x64\xff\x21\x67\xf6\xec\xed\xd4\x19\xdb\x06\xc1" },
{ "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789",
"\xdb\x4b\xfc\xbd\x4d\xa0\xcd\x85\xa6\x0c\x3c\x37\xd3\xfb\xd8\x80"
"\x5c\x77\xf1\x5f\xc6\xb1\xfd\xfe\x61\x4e\xe0\xa7\xc8\xfd\xb4\xc0" },
{ "123456789012345678901234567890123456789012345678901234567890"
"12345678901234567890",
"\xf3\x71\xbc\x4a\x31\x1f\x2b\x00\x9e\xef\x95\x2d\xd8\x3c\xa8\x0e"
"\x2b\x60\x02\x6c\x8e\x93\x55\x92\xd0\xf9\xc3\x08\x45\x3c\x81\x3e" }
};
#define ntests (sizeof (tests) / sizeof (tests[0]))
static const struct
{
const char *salt;
const char *input;
const char *expected;
} tests2[] =
{
{ "$5$saltstring", "Hello world!",
"$5$saltstring$5B8vYYiY.CVt1RlTTf8KbXBH3hsxY/GNooZaBBGWEc5" },
{ "$5$rounds=10000$saltstringsaltstring", "Hello world!",
"$5$rounds=10000$saltstringsaltst$3xv.VbSHBb41AL9AvLeujZkZRBAwqFMz2."
"opqey6IcA" },
{ "$5$rounds=5000$toolongsaltstring", "This is just a test",
"$5$rounds=5000$toolongsaltstrin$Un/5jzAHMgOGZ5.mWJpuVolil07guHPvOW8"
"mGRcvxa5" },
{ "$5$rounds=1400$anotherlongsaltstring",
"a very much longer text to encrypt. This one even stretches over more"
"than one line.",
"$5$rounds=1400$anotherlongsalts$Rx.j8H.h8HjEDGomFU8bDkXm3XIUnzyxf12"
"oP84Bnq1" },
{ "$5$rounds=77777$short",