crypt_blowfish.c raw
1 /* Modified by Rich Felker in for inclusion in musl libc, based on
2 * Solar Designer's second size-optimized version sent to the musl
3 * mailing list. */
4
5 /*
6 * The crypt_blowfish homepage is:
7 *
8 * http://www.openwall.com/crypt/
9 *
10 * This code comes from John the Ripper password cracker, with reentrant
11 * and crypt(3) interfaces added, but optimizations specific to password
12 * cracking removed.
13 *
14 * Written by Solar Designer <solar at openwall.com> in 1998-2012.
15 * No copyright is claimed, and the software is hereby placed in the public
16 * domain. In case this attempt to disclaim copyright and place the software
17 * in the public domain is deemed null and void, then the software is
18 * Copyright (c) 1998-2014 Solar Designer and it is hereby released to the
19 * general public under the following terms:
20 *
21 * Redistribution and use in source and binary forms, with or without
22 * modification, are permitted.
23 *
24 * There's ABSOLUTELY NO WARRANTY, express or implied.
25 *
26 * It is my intent that you should be able to use this on your system,
27 * as part of a software package, or anywhere else to improve security,
28 * ensure compatibility, or for any other purpose. I would appreciate
29 * it if you give credit where it is due and keep your modifications in
30 * the public domain as well, but I don't require that in order to let
31 * you place this code and any modifications you make under a license
32 * of your choice.
33 *
34 * This implementation is fully compatible with OpenBSD's bcrypt.c for prefix
35 * "$2b$", originally by Niels Provos <provos at citi.umich.edu>, and it uses
36 * some of his ideas. The password hashing algorithm was designed by David
37 * Mazieres <dm at lcs.mit.edu>. For information on the level of
38 * compatibility for bcrypt hash prefixes other than "$2b$", please refer to
39 * the comments in BF_set_key() below and to the included crypt(3) man page.
40 *
41 * There's a paper on the algorithm that explains its design decisions:
42 *
43 * http://www.usenix.org/events/usenix99/provos.html
44 *
45 * Some of the tricks in BF_ROUND might be inspired by Eric Young's
46 * Blowfish library (I can't be sure if I would think of something if I
47 * hadn't seen his code).
48 */
49
50 #include <string.h>
51 #include <stdint.h>
52
53 typedef uint32_t BF_word;
54 typedef int32_t BF_word_signed;
55
56 /* Number of Blowfish rounds, this is also hardcoded into a few places */
57 #define BF_N 16
58
59 typedef BF_word BF_key[BF_N + 2];
60
61 typedef union {
62 struct {
63 BF_key P;
64 BF_word S[4][0x100];
65 } s;
66 BF_word PS[BF_N + 2 + 4 * 0x100];
67 } BF_ctx;
68
69 /*
70 * Magic IV for 64 Blowfish encryptions that we do at the end.
71 * The string is "OrpheanBeholderScryDoubt" on big-endian.
72 */
73 static const BF_word BF_magic_w[6] = {
74 0x4F727068, 0x65616E42, 0x65686F6C,
75 0x64657253, 0x63727944, 0x6F756274
76 };
77
78 /*
79 * P-box and S-box tables initialized with digits of Pi.
80 */
81 static const BF_ctx BF_init_state = {{
82 {
83 0x243f6a88, 0x85a308d3, 0x13198a2e, 0x03707344,
84 0xa4093822, 0x299f31d0, 0x082efa98, 0xec4e6c89,
85 0x452821e6, 0x38d01377, 0xbe5466cf, 0x34e90c6c,
86 0xc0ac29b7, 0xc97c50dd, 0x3f84d5b5, 0xb5470917,
87 0x9216d5d9, 0x8979fb1b
88 }, {
89 {
90 0xd1310ba6, 0x98dfb5ac, 0x2ffd72db, 0xd01adfb7,
91 0xb8e1afed, 0x6a267e96, 0xba7c9045, 0xf12c7f99,
92 0x24a19947, 0xb3916cf7, 0x0801f2e2, 0x858efc16,
93 0x636920d8, 0x71574e69, 0xa458fea3, 0xf4933d7e,
94 0x0d95748f, 0x728eb658, 0x718bcd58, 0x82154aee,
95 0x7b54a41d, 0xc25a59b5, 0x9c30d539, 0x2af26013,
96 0xc5d1b023, 0x286085f0, 0xca417918, 0xb8db38ef,
97 0x8e79dcb0, 0x603a180e, 0x6c9e0e8b, 0xb01e8a3e,
98 0xd71577c1, 0xbd314b27, 0x78af2fda, 0x55605c60,
99 0xe65525f3, 0xaa55ab94, 0x57489862, 0x63e81440,
100 0x55ca396a, 0x2aab10b6, 0xb4cc5c34, 0x1141e8ce,
101 0xa15486af, 0x7c72e993, 0xb3ee1411, 0x636fbc2a,
102 0x2ba9c55d, 0x741831f6, 0xce5c3e16, 0x9b87931e,
103 0xafd6ba33, 0x6c24cf5c, 0x7a325381, 0x28958677,
104 0x3b8f4898, 0x6b4bb9af, 0xc4bfe81b, 0x66282193,
105 0x61d809cc, 0xfb21a991, 0x487cac60, 0x5dec8032,
106 0xef845d5d, 0xe98575b1, 0xdc262302, 0xeb651b88,
107 0x23893e81, 0xd396acc5, 0x0f6d6ff3, 0x83f44239,
108 0x2e0b4482, 0xa4842004, 0x69c8f04a, 0x9e1f9b5e,
109 0x21c66842, 0xf6e96c9a, 0x670c9c61, 0xabd388f0,
110 0x6a51a0d2, 0xd8542f68, 0x960fa728, 0xab5133a3,
111 0x6eef0b6c, 0x137a3be4, 0xba3bf050, 0x7efb2a98,
112 0xa1f1651d, 0x39af0176, 0x66ca593e, 0x82430e88,
113 0x8cee8619, 0x456f9fb4, 0x7d84a5c3, 0x3b8b5ebe,
114 0xe06f75d8, 0x85c12073, 0x401a449f, 0x56c16aa6,
115 0x4ed3aa62, 0x363f7706, 0x1bfedf72, 0x429b023d,
116 0x37d0d724, 0xd00a1248, 0xdb0fead3, 0x49f1c09b,
117 0x075372c9, 0x80991b7b, 0x25d479d8, 0xf6e8def7,
118 0xe3fe501a, 0xb6794c3b, 0x976ce0bd, 0x04c006ba,
119 0xc1a94fb6, 0x409f60c4, 0x5e5c9ec2, 0x196a2463,
120 0x68fb6faf, 0x3e6c53b5, 0x1339b2eb, 0x3b52ec6f,
121 0x6dfc511f, 0x9b30952c, 0xcc814544, 0xaf5ebd09,
122 0xbee3d004, 0xde334afd, 0x660f2807, 0x192e4bb3,
123 0xc0cba857, 0x45c8740f, 0xd20b5f39, 0xb9d3fbdb,
124 0x5579c0bd, 0x1a60320a, 0xd6a100c6, 0x402c7279,
125 0x679f25fe, 0xfb1fa3cc, 0x8ea5e9f8, 0xdb3222f8,
126 0x3c7516df, 0xfd616b15, 0x2f501ec8, 0xad0552ab,
127 0x323db5fa, 0xfd238760, 0x53317b48, 0x3e00df82,
128 0x9e5c57bb, 0xca6f8ca0, 0x1a87562e, 0xdf1769db,
129 0xd542a8f6, 0x287effc3, 0xac6732c6, 0x8c4f5573,
130 0x695b27b0, 0xbbca58c8, 0xe1ffa35d, 0xb8f011a0,
131 0x10fa3d98, 0xfd2183b8, 0x4afcb56c, 0x2dd1d35b,
132 0x9a53e479, 0xb6f84565, 0xd28e49bc, 0x4bfb9790,
133 0xe1ddf2da, 0xa4cb7e33, 0x62fb1341, 0xcee4c6e8,
134 0xef20cada, 0x36774c01, 0xd07e9efe, 0x2bf11fb4,
135 0x95dbda4d, 0xae909198, 0xeaad8e71, 0x6b93d5a0,
136 0xd08ed1d0, 0xafc725e0, 0x8e3c5b2f, 0x8e7594b7,
137 0x8ff6e2fb, 0xf2122b64, 0x8888b812, 0x900df01c,
138 0x4fad5ea0, 0x688fc31c, 0xd1cff191, 0xb3a8c1ad,
139 0x2f2f2218, 0xbe0e1777, 0xea752dfe, 0x8b021fa1,
140 0xe5a0cc0f, 0xb56f74e8, 0x18acf3d6, 0xce89e299,
141 0xb4a84fe0, 0xfd13e0b7, 0x7cc43b81, 0xd2ada8d9,
142 0x165fa266, 0x80957705, 0x93cc7314, 0x211a1477,
143 0xe6ad2065, 0x77b5fa86, 0xc75442f5, 0xfb9d35cf,
144 0xebcdaf0c, 0x7b3e89a0, 0xd6411bd3, 0xae1e7e49,
145 0x00250e2d, 0x2071b35e, 0x226800bb, 0x57b8e0af,
146 0x2464369b, 0xf009b91e, 0x5563911d, 0x59dfa6aa,
147 0x78c14389, 0xd95a537f, 0x207d5ba2, 0x02e5b9c5,
148 0x83260376, 0x6295cfa9, 0x11c81968, 0x4e734a41,
149 0xb3472dca, 0x7b14a94a, 0x1b510052, 0x9a532915,
150 0xd60f573f, 0xbc9bc6e4, 0x2b60a476, 0x81e67400,
151 0x08ba6fb5, 0x571be91f, 0xf296ec6b, 0x2a0dd915,
152 0xb6636521, 0xe7b9f9b6, 0xff34052e, 0xc5855664,
153 0x53b02d5d, 0xa99f8fa1, 0x08ba4799, 0x6e85076a
154 }, {
155 0x4b7a70e9, 0xb5b32944, 0xdb75092e, 0xc4192623,
156 0xad6ea6b0, 0x49a7df7d, 0x9cee60b8, 0x8fedb266,
157 0xecaa8c71, 0x699a17ff, 0x5664526c, 0xc2b19ee1,
158 0x193602a5, 0x75094c29, 0xa0591340, 0xe4183a3e,
159 0x3f54989a, 0x5b429d65, 0x6b8fe4d6, 0x99f73fd6,
160 0xa1d29c07, 0xefe830f5, 0x4d2d38e6, 0xf0255dc1,
161 0x4cdd2086, 0x8470eb26, 0x6382e9c6, 0x021ecc5e,
162 0x09686b3f, 0x3ebaefc9, 0x3c971814, 0x6b6a70a1,
163 0x687f3584, 0x52a0e286, 0xb79c5305, 0xaa500737,
164 0x3e07841c, 0x7fdeae5c, 0x8e7d44ec, 0x5716f2b8,
165 0xb03ada37, 0xf0500c0d, 0xf01c1f04, 0x0200b3ff,
166 0xae0cf51a, 0x3cb574b2, 0x25837a58, 0xdc0921bd,
167 0xd19113f9, 0x7ca92ff6, 0x94324773, 0x22f54701,
168 0x3ae5e581, 0x37c2dadc, 0xc8b57634, 0x9af3dda7,
169 0xa9446146, 0x0fd0030e, 0xecc8c73e, 0xa4751e41,
170 0xe238cd99, 0x3bea0e2f, 0x3280bba1, 0x183eb331,
171 0x4e548b38, 0x4f6db908, 0x6f420d03, 0xf60a04bf,
172 0x2cb81290, 0x24977c79, 0x5679b072, 0xbcaf89af,
173 0xde9a771f, 0xd9930810, 0xb38bae12, 0xdccf3f2e,
174 0x5512721f, 0x2e6b7124, 0x501adde6, 0x9f84cd87,
175 0x7a584718, 0x7408da17, 0xbc9f9abc, 0xe94b7d8c,
176 0xec7aec3a, 0xdb851dfa, 0x63094366, 0xc464c3d2,
177 0xef1c1847, 0x3215d908, 0xdd433b37, 0x24c2ba16,
178 0x12a14d43, 0x2a65c451, 0x50940002, 0x133ae4dd,
179 0x71dff89e, 0x10314e55, 0x81ac77d6, 0x5f11199b,
180 0x043556f1, 0xd7a3c76b, 0x3c11183b, 0x5924a509,
181 0xf28fe6ed, 0x97f1fbfa, 0x9ebabf2c, 0x1e153c6e,
182 0x86e34570, 0xeae96fb1, 0x860e5e0a, 0x5a3e2ab3,
183 0x771fe71c, 0x4e3d06fa, 0x2965dcb9, 0x99e71d0f,
184 0x803e89d6, 0x5266c825, 0x2e4cc978, 0x9c10b36a,
185 0xc6150eba, 0x94e2ea78, 0xa5fc3c53, 0x1e0a2df4,
186 0xf2f74ea7, 0x361d2b3d, 0x1939260f, 0x19c27960,
187 0x5223a708, 0xf71312b6, 0xebadfe6e, 0xeac31f66,
188 0xe3bc4595, 0xa67bc883, 0xb17f37d1, 0x018cff28,
189 0xc332ddef, 0xbe6c5aa5, 0x65582185, 0x68ab9802,
190 0xeecea50f, 0xdb2f953b, 0x2aef7dad, 0x5b6e2f84,
191 0x1521b628, 0x29076170, 0xecdd4775, 0x619f1510,
192 0x13cca830, 0xeb61bd96, 0x0334fe1e, 0xaa0363cf,
193 0xb5735c90, 0x4c70a239, 0xd59e9e0b, 0xcbaade14,
194 0xeecc86bc, 0x60622ca7, 0x9cab5cab, 0xb2f3846e,
195 0x648b1eaf, 0x19bdf0ca, 0xa02369b9, 0x655abb50,
196 0x40685a32, 0x3c2ab4b3, 0x319ee9d5, 0xc021b8f7,
197 0x9b540b19, 0x875fa099, 0x95f7997e, 0x623d7da8,
198 0xf837889a, 0x97e32d77, 0x11ed935f, 0x16681281,
199 0x0e358829, 0xc7e61fd6, 0x96dedfa1, 0x7858ba99,
200 0x57f584a5, 0x1b227263, 0x9b83c3ff, 0x1ac24696,
201 0xcdb30aeb, 0x532e3054, 0x8fd948e4, 0x6dbc3128,
202 0x58ebf2ef, 0x34c6ffea, 0xfe28ed61, 0xee7c3c73,
203 0x5d4a14d9, 0xe864b7e3, 0x42105d14, 0x203e13e0,
204 0x45eee2b6, 0xa3aaabea, 0xdb6c4f15, 0xfacb4fd0,
205 0xc742f442, 0xef6abbb5, 0x654f3b1d, 0x41cd2105,
206 0xd81e799e, 0x86854dc7, 0xe44b476a, 0x3d816250,
207 0xcf62a1f2, 0x5b8d2646, 0xfc8883a0, 0xc1c7b6a3,
208 0x7f1524c3, 0x69cb7492, 0x47848a0b, 0x5692b285,
209 0x095bbf00, 0xad19489d, 0x1462b174, 0x23820e00,
210 0x58428d2a, 0x0c55f5ea, 0x1dadf43e, 0x233f7061,
211 0x3372f092, 0x8d937e41, 0xd65fecf1, 0x6c223bdb,
212 0x7cde3759, 0xcbee7460, 0x4085f2a7, 0xce77326e,
213 0xa6078084, 0x19f8509e, 0xe8efd855, 0x61d99735,
214 0xa969a7aa, 0xc50c06c2, 0x5a04abfc, 0x800bcadc,
215 0x9e447a2e, 0xc3453484, 0xfdd56705, 0x0e1e9ec9,
216 0xdb73dbd3, 0x105588cd, 0x675fda79, 0xe3674340,
217 0xc5c43465, 0x713e38d8, 0x3d28f89e, 0xf16dff20,
218 0x153e21e7, 0x8fb03d4a, 0xe6e39f2b, 0xdb83adf7
219 }, {
220 0xe93d5a68, 0x948140f7, 0xf64c261c, 0x94692934,
221 0x411520f7, 0x7602d4f7, 0xbcf46b2e, 0xd4a20068,
222 0xd4082471, 0x3320f46a, 0x43b7d4b7, 0x500061af,
223 0x1e39f62e, 0x97244546, 0x14214f74, 0xbf8b8840,
224 0x4d95fc1d, 0x96b591af, 0x70f4ddd3, 0x66a02f45,
225 0xbfbc09ec, 0x03bd9785, 0x7fac6dd0, 0x31cb8504,
226 0x96eb27b3, 0x55fd3941, 0xda2547e6, 0xabca0a9a,
227 0x28507825, 0x530429f4, 0x0a2c86da, 0xe9b66dfb,
228 0x68dc1462, 0xd7486900, 0x680ec0a4, 0x27a18dee,
229 0x4f3ffea2, 0xe887ad8c, 0xb58ce006, 0x7af4d6b6,
230 0xaace1e7c, 0xd3375fec, 0xce78a399, 0x406b2a42,
231 0x20fe9e35, 0xd9f385b9, 0xee39d7ab, 0x3b124e8b,
232 0x1dc9faf7, 0x4b6d1856, 0x26a36631, 0xeae397b2,
233 0x3a6efa74, 0xdd5b4332, 0x6841e7f7, 0xca7820fb,
234 0xfb0af54e, 0xd8feb397, 0x454056ac, 0xba489527,
235 0x55533a3a, 0x20838d87, 0xfe6ba9b7, 0xd096954b,
236 0x55a867bc, 0xa1159a58, 0xcca92963, 0x99e1db33,
237 0xa62a4a56, 0x3f3125f9, 0x5ef47e1c, 0x9029317c,
238 0xfdf8e802, 0x04272f70, 0x80bb155c, 0x05282ce3,
239 0x95c11548, 0xe4c66d22, 0x48c1133f, 0xc70f86dc,
240 0x07f9c9ee, 0x41041f0f, 0x404779a4, 0x5d886e17,
241 0x325f51eb, 0xd59bc0d1, 0xf2bcc18f, 0x41113564,
242 0x257b7834, 0x602a9c60, 0xdff8e8a3, 0x1f636c1b,
243 0x0e12b4c2, 0x02e1329e, 0xaf664fd1, 0xcad18115,
244 0x6b2395e0, 0x333e92e1, 0x3b240b62, 0xeebeb922,
245 0x85b2a20e, 0xe6ba0d99, 0xde720c8c, 0x2da2f728,
246 0xd0127845, 0x95b794fd, 0x647d0862, 0xe7ccf5f0,
247 0x5449a36f, 0x877d48fa, 0xc39dfd27, 0xf33e8d1e,
248 0x0a476341, 0x992eff74, 0x3a6f6eab, 0xf4f8fd37,
249 0xa812dc60, 0xa1ebddf8, 0x991be14c, 0xdb6e6b0d,
250 0xc67b5510, 0x6d672c37, 0x2765d43b, 0xdcd0e804,
251 0xf1290dc7, 0xcc00ffa3, 0xb5390f92, 0x690fed0b,
252 0x667b9ffb, 0xcedb7d9c, 0xa091cf0b, 0xd9155ea3,
253 0xbb132f88, 0x515bad24, 0x7b9479bf, 0x763bd6eb,
254 0x37392eb3, 0xcc115979, 0x8026e297, 0xf42e312d,
255 0x6842ada7, 0xc66a2b3b, 0x12754ccc, 0x782ef11c,
256 0x6a124237, 0xb79251e7, 0x06a1bbe6, 0x4bfb6350,
257 0x1a6b1018, 0x11caedfa, 0x3d25bdd8, 0xe2e1c3c9,
258 0x44421659, 0x0a121386, 0xd90cec6e, 0xd5abea2a,
259 0x64af674e, 0xda86a85f, 0xbebfe988, 0x64e4c3fe,
260 0x9dbc8057, 0xf0f7c086, 0x60787bf8, 0x6003604d,
261 0xd1fd8346, 0xf6381fb0, 0x7745ae04, 0xd736fccc,
262 0x83426b33, 0xf01eab71, 0xb0804187, 0x3c005e5f,
263 0x77a057be, 0xbde8ae24, 0x55464299, 0xbf582e61,
264 0x4e58f48f, 0xf2ddfda2, 0xf474ef38, 0x8789bdc2,
265 0x5366f9c3, 0xc8b38e74, 0xb475f255, 0x46fcd9b9,
266 0x7aeb2661, 0x8b1ddf84, 0x846a0e79, 0x915f95e2,
267 0x466e598e, 0x20b45770, 0x8cd55591, 0xc902de4c,
268 0xb90bace1, 0xbb8205d0, 0x11a86248, 0x7574a99e,
269 0xb77f19b6, 0xe0a9dc09, 0x662d09a1, 0xc4324633,
270 0xe85a1f02, 0x09f0be8c, 0x4a99a025, 0x1d6efe10,
271 0x1ab93d1d, 0x0ba5a4df, 0xa186f20f, 0x2868f169,
272 0xdcb7da83, 0x573906fe, 0xa1e2ce9b, 0x4fcd7f52,
273 0x50115e01, 0xa70683fa, 0xa002b5c4, 0x0de6d027,
274 0x9af88c27, 0x773f8641, 0xc3604c06, 0x61a806b5,
275 0xf0177a28, 0xc0f586e0, 0x006058aa, 0x30dc7d62,
276 0x11e69ed7, 0x2338ea63, 0x53c2dd94, 0xc2c21634,
277 0xbbcbee56, 0x90bcb6de, 0xebfc7da1, 0xce591d76,
278 0x6f05e409, 0x4b7c0188, 0x39720a3d, 0x7c927c24,
279 0x86e3725f, 0x724d9db9, 0x1ac15bb4, 0xd39eb8fc,
280 0xed545578, 0x08fca5b5, 0xd83d7cd3, 0x4dad0fc4,
281 0x1e50ef5e, 0xb161e6f8, 0xa28514d9, 0x6c51133c,
282 0x6fd5c7e7, 0x56e14ec4, 0x362abfce, 0xddc6c837,
283 0xd79a3234, 0x92638212, 0x670efa8e, 0x406000e0
284 }, {
285 0x3a39ce37, 0xd3faf5cf, 0xabc27737, 0x5ac52d1b,
286 0x5cb0679e, 0x4fa33742, 0xd3822740, 0x99bc9bbe,
287 0xd5118e9d, 0xbf0f7315, 0xd62d1c7e, 0xc700c47b,
288 0xb78c1b6b, 0x21a19045, 0xb26eb1be, 0x6a366eb4,
289 0x5748ab2f, 0xbc946e79, 0xc6a376d2, 0x6549c2c8,
290 0x530ff8ee, 0x468dde7d, 0xd5730a1d, 0x4cd04dc6,
291 0x2939bbdb, 0xa9ba4650, 0xac9526e8, 0xbe5ee304,
292 0xa1fad5f0, 0x6a2d519a, 0x63ef8ce2, 0x9a86ee22,
293 0xc089c2b8, 0x43242ef6, 0xa51e03aa, 0x9cf2d0a4,
294 0x83c061ba, 0x9be96a4d, 0x8fe51550, 0xba645bd6,
295 0x2826a2f9, 0xa73a3ae1, 0x4ba99586, 0xef5562e9,
296 0xc72fefd3, 0xf752f7da, 0x3f046f69, 0x77fa0a59,
297 0x80e4a915, 0x87b08601, 0x9b09e6ad, 0x3b3ee593,
298 0xe990fd5a, 0x9e34d797, 0x2cf0b7d9, 0x022b8b51,
299 0x96d5ac3a, 0x017da67d, 0xd1cf3ed6, 0x7c7d2d28,
300 0x1f9f25cf, 0xadf2b89b, 0x5ad6b472, 0x5a88f54c,
301 0xe029ac71, 0xe019a5e6, 0x47b0acfd, 0xed93fa9b,
302 0xe8d3c48d, 0x283b57cc, 0xf8d56629, 0x79132e28,
303 0x785f0191, 0xed756055, 0xf7960e44, 0xe3d35e8c,
304 0x15056dd4, 0x88f46dba, 0x03a16125, 0x0564f0bd,
305 0xc3eb9e15, 0x3c9057a2, 0x97271aec, 0xa93a072a,
306 0x1b3f6d9b, 0x1e6321f5, 0xf59c66fb, 0x26dcf319,
307 0x7533d928, 0xb155fdf5, 0x03563482, 0x8aba3cbb,
308 0x28517711, 0xc20ad9f8, 0xabcc5167, 0xccad925f,
309 0x4de81751, 0x3830dc8e, 0x379d5862, 0x9320f991,
310 0xea7a90c2, 0xfb3e7bce, 0x5121ce64, 0x774fbe32,
311 0xa8b6e37e, 0xc3293d46, 0x48de5369, 0x6413e680,
312 0xa2ae0810, 0xdd6db224, 0x69852dfd, 0x09072166,
313 0xb39a460a, 0x6445c0dd, 0x586cdecf, 0x1c20c8ae,
314 0x5bbef7dd, 0x1b588d40, 0xccd2017f, 0x6bb4e3bb,
315 0xdda26a7e, 0x3a59ff45, 0x3e350a44, 0xbcb4cdd5,
316 0x72eacea8, 0xfa6484bb, 0x8d6612ae, 0xbf3c6f47,
317 0xd29be463, 0x542f5d9e, 0xaec2771b, 0xf64e6370,
318 0x740e0d8d, 0xe75b1357, 0xf8721671, 0xaf537d5d,
319 0x4040cb08, 0x4eb4e2cc, 0x34d2466a, 0x0115af84,
320 0xe1b00428, 0x95983a1d, 0x06b89fb4, 0xce6ea048,
321 0x6f3f3b82, 0x3520ab82, 0x011a1d4b, 0x277227f8,
322 0x611560b1, 0xe7933fdc, 0xbb3a792b, 0x344525bd,
323 0xa08839e1, 0x51ce794b, 0x2f32c9b7, 0xa01fbac9,
324 0xe01cc87e, 0xbcc7d1f6, 0xcf0111c3, 0xa1e8aac7,
325 0x1a908749, 0xd44fbd9a, 0xd0dadecb, 0xd50ada38,
326 0x0339c32a, 0xc6913667, 0x8df9317c, 0xe0b12b4f,
327 0xf79e59b7, 0x43f5bb3a, 0xf2d519ff, 0x27d9459c,
328 0xbf97222c, 0x15e6fc2a, 0x0f91fc71, 0x9b941525,
329 0xfae59361, 0xceb69ceb, 0xc2a86459, 0x12baa8d1,
330 0xb6c1075e, 0xe3056a0c, 0x10d25065, 0xcb03a442,
331 0xe0ec6e0e, 0x1698db3b, 0x4c98a0be, 0x3278e964,
332 0x9f1f9532, 0xe0d392df, 0xd3a0342b, 0x8971f21e,
333 0x1b0a7441, 0x4ba3348c, 0xc5be7120, 0xc37632d8,
334 0xdf359f8d, 0x9b992f2e, 0xe60b6f47, 0x0fe3f11d,
335 0xe54cda54, 0x1edad891, 0xce6279cf, 0xcd3e7e6f,
336 0x1618b166, 0xfd2c1d05, 0x848fd2c5, 0xf6fb2299,
337 0xf523f357, 0xa6327623, 0x93a83531, 0x56cccd02,
338 0xacf08162, 0x5a75ebb5, 0x6e163697, 0x88d273cc,
339 0xde966292, 0x81b949d0, 0x4c50901b, 0x71c65614,
340 0xe6c6c7bd, 0x327a140a, 0x45e1d006, 0xc3f27b9a,
341 0xc9aa53fd, 0x62a80f00, 0xbb25bfe2, 0x35bdd2f6,
342 0x71126905, 0xb2040222, 0xb6cbcf7c, 0xcd769c2b,
343 0x53113ec0, 0x1640e3d3, 0x38abbd60, 0x2547adf0,
344 0xba38209c, 0xf746ce76, 0x77afa1c5, 0x20756060,
345 0x85cbfe4e, 0x8ae88dd8, 0x7aaaf9b0, 0x4cf9aa7e,
346 0x1948c25c, 0x02fb8a8c, 0x01c36ae4, 0xd6ebe1f9,
347 0x90d4f869, 0xa65cdea0, 0x3f09252d, 0xc208e69f,
348 0xb74e6132, 0xce77e25b, 0x578fdfe3, 0x3ac372e6
349 }
350 }
351 }};
352
353 static const unsigned char BF_itoa64[64 + 1] =
354 "./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
355
356 static const unsigned char BF_atoi64[0x60] = {
357 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 0, 1,
358 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 64, 64, 64, 64, 64,
359 64, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
360 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 64, 64, 64, 64, 64,
361 64, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42,
362 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 64, 64, 64, 64, 64
363 };
364
365 #define BF_safe_atoi64(dst, src) \
366 { \
367 tmp = (unsigned char)(src); \
368 if ((unsigned int)(tmp -= 0x20) >= 0x60) return -1; \
369 tmp = BF_atoi64[tmp]; \
370 if (tmp > 63) return -1; \
371 (dst) = tmp; \
372 }
373
374 static int BF_decode(BF_word *dst, const char *src, int size)
375 {
376 unsigned char *dptr = (unsigned char *)dst;
377 unsigned char *end = dptr + size;
378 const unsigned char *sptr = (const unsigned char *)src;
379 unsigned int tmp, c1, c2, c3, c4;
380
381 do {
382 BF_safe_atoi64(c1, *sptr++);
383 BF_safe_atoi64(c2, *sptr++);
384 *dptr++ = (c1 << 2) | ((c2 & 0x30) >> 4);
385 if (dptr >= end) break;
386
387 BF_safe_atoi64(c3, *sptr++);
388 *dptr++ = ((c2 & 0x0F) << 4) | ((c3 & 0x3C) >> 2);
389 if (dptr >= end) break;
390
391 BF_safe_atoi64(c4, *sptr++);
392 *dptr++ = ((c3 & 0x03) << 6) | c4;
393 } while (dptr < end);
394
395 return 0;
396 }
397
398 static void BF_encode(char *dst, const BF_word *src, int size)
399 {
400 const unsigned char *sptr = (const unsigned char *)src;
401 const unsigned char *end = sptr + size;
402 unsigned char *dptr = (unsigned char *)dst;
403 unsigned int c1, c2;
404
405 do {
406 c1 = *sptr++;
407 *dptr++ = BF_itoa64[c1 >> 2];
408 c1 = (c1 & 0x03) << 4;
409 if (sptr >= end) {
410 *dptr++ = BF_itoa64[c1];
411 break;
412 }
413
414 c2 = *sptr++;
415 c1 |= c2 >> 4;
416 *dptr++ = BF_itoa64[c1];
417 c1 = (c2 & 0x0f) << 2;
418 if (sptr >= end) {
419 *dptr++ = BF_itoa64[c1];
420 break;
421 }
422
423 c2 = *sptr++;
424 c1 |= c2 >> 6;
425 *dptr++ = BF_itoa64[c1];
426 *dptr++ = BF_itoa64[c2 & 0x3f];
427 } while (sptr < end);
428 }
429
430 static void BF_swap(BF_word *x, int count)
431 {
432 if ((union { int i; char c; }){1}.c)
433 do {
434 BF_word tmp = *x;
435 tmp = (tmp << 16) | (tmp >> 16);
436 *x++ = ((tmp & 0x00FF00FF) << 8) | ((tmp >> 8) & 0x00FF00FF);
437 } while (--count);
438 }
439
440 #define BF_ROUND(L, R, N) \
441 tmp1 = L & 0xFF; \
442 tmp2 = L >> 8; \
443 tmp2 &= 0xFF; \
444 tmp3 = L >> 16; \
445 tmp3 &= 0xFF; \
446 tmp4 = L >> 24; \
447 tmp1 = ctx->s.S[3][tmp1]; \
448 tmp2 = ctx->s.S[2][tmp2]; \
449 tmp3 = ctx->s.S[1][tmp3]; \
450 tmp3 += ctx->s.S[0][tmp4]; \
451 tmp3 ^= tmp2; \
452 R ^= ctx->s.P[N + 1]; \
453 tmp3 += tmp1; \
454 R ^= tmp3;
455
456 static BF_word BF_encrypt(BF_ctx *ctx,
457 BF_word L, BF_word R,
458 BF_word *start, BF_word *end)
459 {
460 BF_word tmp1, tmp2, tmp3, tmp4;
461 BF_word *ptr = start;
462
463 do {
464 L ^= ctx->s.P[0];
465 #if 0
466 BF_ROUND(L, R, 0);
467 BF_ROUND(R, L, 1);
468 BF_ROUND(L, R, 2);
469 BF_ROUND(R, L, 3);
470 BF_ROUND(L, R, 4);
471 BF_ROUND(R, L, 5);
472 BF_ROUND(L, R, 6);
473 BF_ROUND(R, L, 7);
474 BF_ROUND(L, R, 8);
475 BF_ROUND(R, L, 9);
476 BF_ROUND(L, R, 10);
477 BF_ROUND(R, L, 11);
478 BF_ROUND(L, R, 12);
479 BF_ROUND(R, L, 13);
480 BF_ROUND(L, R, 14);
481 BF_ROUND(R, L, 15);
482 #else
483 for (int i=0; i<16; i+=2) {
484 BF_ROUND(L, R, i);
485 BF_ROUND(R, L, i+1);
486 }
487 #endif
488 tmp4 = R;
489 R = L;
490 L = tmp4 ^ ctx->s.P[BF_N + 1];
491 *ptr++ = L;
492 *ptr++ = R;
493 } while (ptr < end);
494
495 return L;
496 }
497
498 static void BF_set_key(const char *key, BF_key expanded, BF_key initial,
499 unsigned char flags)
500 {
501 const char *ptr = key;
502 unsigned int bug, i, j;
503 BF_word safety, sign, diff, tmp[2];
504
505 /*
506 * There was a sign extension bug in older revisions of this function. While
507 * we would have liked to simply fix the bug and move on, we have to provide
508 * a backwards compatibility feature (essentially the bug) for some systems and
509 * a safety measure for some others. The latter is needed because for certain
510 * multiple inputs to the buggy algorithm there exist easily found inputs to
511 * the correct algorithm that produce the same hash. Thus, we optionally
512 * deviate from the correct algorithm just enough to avoid such collisions.
513 * While the bug itself affected the majority of passwords containing
514 * characters with the 8th bit set (although only a percentage of those in a
515 * collision-producing way), the anti-collision safety measure affects
516 * only a subset of passwords containing the '\xff' character (not even all of
517 * those passwords, just some of them). This character is not found in valid
518 * UTF-8 sequences and is rarely used in popular 8-bit character encodings.
519 * Thus, the safety measure is unlikely to cause much annoyance, and is a
520 * reasonable tradeoff to use when authenticating against existing hashes that
521 * are not reliably known to have been computed with the correct algorithm.
522 *
523 * We use an approach that tries to minimize side-channel leaks of password
524 * information - that is, we mostly use fixed-cost bitwise operations instead
525 * of branches or table lookups. (One conditional branch based on password
526 * length remains. It is not part of the bug aftermath, though, and is
527 * difficult and possibly unreasonable to avoid given the use of C strings by
528 * the caller, which results in similar timing leaks anyway.)
529 *
530 * For actual implementation, we set an array index in the variable "bug"
531 * (0 means no bug, 1 means sign extension bug emulation) and a flag in the
532 * variable "safety" (bit 16 is set when the safety measure is requested).
533 * Valid combinations of settings are:
534 *
535 * Prefix "$2a$": bug = 0, safety = 0x10000
536 * Prefix "$2b$": bug = 0, safety = 0
537 * Prefix "$2x$": bug = 1, safety = 0
538 * Prefix "$2y$": bug = 0, safety = 0
539 */
540 bug = flags & 1;
541 safety = ((BF_word)flags & 2) << 15;
542
543 sign = diff = 0;
544
545 for (i = 0; i < BF_N + 2; i++) {
546 tmp[0] = tmp[1] = 0;
547 for (j = 0; j < 4; j++) {
548 tmp[0] <<= 8;
549 tmp[0] |= (unsigned char)*ptr; /* correct */
550 tmp[1] <<= 8;
551 tmp[1] |= (signed char)*ptr; /* bug */
552 /*
553 * Sign extension in the first char has no effect - nothing to overwrite yet,
554 * and those extra 24 bits will be fully shifted out of the 32-bit word. For
555 * chars 2, 3, 4 in each four-char block, we set bit 7 of "sign" if sign
556 * extension in tmp[1] occurs. Once this flag is set, it remains set.
557 */
558 if (j)
559 sign |= tmp[1] & 0x80;
560 if (!*ptr)
561 ptr = key;
562 else
563 ptr++;
564 }
565 diff |= tmp[0] ^ tmp[1]; /* Non-zero on any differences */
566
567 expanded[i] = tmp[bug];
568 initial[i] = BF_init_state.s.P[i] ^ tmp[bug];
569 }
570
571 /*
572 * At this point, "diff" is zero iff the correct and buggy algorithms produced
573 * exactly the same result. If so and if "sign" is non-zero, which indicates
574 * that there was a non-benign sign extension, this means that we have a
575 * collision between the correctly computed hash for this password and a set of
576 * passwords that could be supplied to the buggy algorithm. Our safety measure
577 * is meant to protect from such many-buggy to one-correct collisions, by
578 * deviating from the correct algorithm in such cases. Let's check for this.
579 */
580 diff |= diff >> 16; /* still zero iff exact match */
581 diff &= 0xffff; /* ditto */
582 diff += 0xffff; /* bit 16 set iff "diff" was non-zero (on non-match) */
583 sign <<= 9; /* move the non-benign sign extension flag to bit 16 */
584 sign &= ~diff & safety; /* action needed? */
585
586 /*
587 * If we have determined that we need to deviate from the correct algorithm,
588 * flip bit 16 in initial expanded key. (The choice of 16 is arbitrary, but
589 * let's stick to it now. It came out of the approach we used above, and it's
590 * not any worse than any other choice we could make.)
591 *
592 * It is crucial that we don't do the same to the expanded key used in the main
593 * Eksblowfish loop. By doing it to only one of these two, we deviate from a
594 * state that could be directly specified by a password to the buggy algorithm
595 * (and to the fully correct one as well, but that's a side-effect).
596 */
597 initial[0] ^= sign;
598 }
599
600 static const unsigned char flags_by_subtype[26] = {
601 2, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
602 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 4, 0
603 };
604
605 static char *BF_crypt(const char *key, const char *setting,
606 char *output, BF_word min)
607 {
608 struct {
609 BF_ctx ctx;
610 BF_key expanded_key;
611 union {
612 BF_word salt[4];
613 BF_word output[6];
614 } binary;
615 } data;
616 BF_word count;
617 int i;
618
619 if (setting[0] != '$' ||
620 setting[1] != '2' ||
621 setting[2] - 'a' > 25U ||
622 !flags_by_subtype[setting[2] - 'a'] ||
623 setting[3] != '$' ||
624 setting[4] - '0' > 1U ||
625 setting[5] - '0' > 9U ||
626 setting[6] != '$') {
627 return NULL;
628 }
629
630 count = (BF_word)1 << ((setting[4] - '0') * 10 + (setting[5] - '0'));
631 if (count < min || BF_decode(data.binary.salt, &setting[7], 16)) {
632 return NULL;
633 }
634 BF_swap(data.binary.salt, 4);
635
636 BF_set_key(key, data.expanded_key, data.ctx.s.P,
637 flags_by_subtype[setting[2] - 'a']);
638
639 memcpy(data.ctx.s.S, BF_init_state.s.S, sizeof(data.ctx.s.S));
640
641 {
642 BF_word L = 0, R = 0;
643 BF_word *ptr = &data.ctx.PS[0];
644 do {
645 L = BF_encrypt(&data.ctx,
646 L ^ data.binary.salt[0], R ^ data.binary.salt[1],
647 ptr, ptr);
648 R = *(ptr + 1);
649 ptr += 2;
650
651 if (ptr >= &data.ctx.PS[BF_N + 2 + 4 * 0x100])
652 break;
653
654 L = BF_encrypt(&data.ctx,
655 L ^ data.binary.salt[2], R ^ data.binary.salt[3],
656 ptr, ptr);
657 R = *(ptr + 1);
658 ptr += 2;
659 } while (1);
660 }
661
662 do {
663 int done;
664
665 for (i = 0; i < BF_N + 2; i += 2) {
666 data.ctx.s.P[i] ^= data.expanded_key[i];
667 data.ctx.s.P[i + 1] ^= data.expanded_key[i + 1];
668 }
669
670 done = 0;
671 do {
672 BF_encrypt(&data.ctx, 0, 0,
673 &data.ctx.PS[0],
674 &data.ctx.PS[BF_N + 2 + 4 * 0x100]);
675
676 if (done)
677 break;
678 done = 1;
679
680 {
681 BF_word tmp1, tmp2, tmp3, tmp4;
682
683 tmp1 = data.binary.salt[0];
684 tmp2 = data.binary.salt[1];
685 tmp3 = data.binary.salt[2];
686 tmp4 = data.binary.salt[3];
687 for (i = 0; i < BF_N; i += 4) {
688 data.ctx.s.P[i] ^= tmp1;
689 data.ctx.s.P[i + 1] ^= tmp2;
690 data.ctx.s.P[i + 2] ^= tmp3;
691 data.ctx.s.P[i + 3] ^= tmp4;
692 }
693 data.ctx.s.P[16] ^= tmp1;
694 data.ctx.s.P[17] ^= tmp2;
695 }
696 } while (1);
697 } while (--count);
698
699 for (i = 0; i < 6; i += 2) {
700 BF_word L, LR[2];
701
702 L = BF_magic_w[i];
703 LR[1] = BF_magic_w[i + 1];
704
705 count = 64;
706 do {
707 L = BF_encrypt(&data.ctx, L, LR[1],
708 &LR[0], &LR[0]);
709 } while (--count);
710
711 data.binary.output[i] = L;
712 data.binary.output[i + 1] = LR[1];
713 }
714
715 memcpy(output, setting, 7 + 22 - 1);
716 output[7 + 22 - 1] = BF_itoa64[
717 BF_atoi64[setting[7 + 22 - 1] - 0x20] & 0x30];
718
719 /* This has to be bug-compatible with the original implementation, so
720 * only encode 23 of the 24 bytes. :-) */
721 BF_swap(data.binary.output, 6);
722 BF_encode(&output[7 + 22], data.binary.output, 23);
723 output[7 + 22 + 31] = '\0';
724
725 return output;
726 }
727
728 /*
729 * Please preserve the runtime self-test. It serves two purposes at once:
730 *
731 * 1. We really can't afford the risk of producing incompatible hashes e.g.
732 * when there's something like gcc bug 26587 again, whereas an application or
733 * library integrating this code might not also integrate our external tests or
734 * it might not run them after every build. Even if it does, the miscompile
735 * might only occur on the production build, but not on a testing build (such
736 * as because of different optimization settings). It is painful to recover
737 * from incorrectly-computed hashes - merely fixing whatever broke is not
738 * enough. Thus, a proactive measure like this self-test is needed.
739 *
740 * 2. We don't want to leave sensitive data from our actual password hash
741 * computation on the stack or in registers. Previous revisions of the code
742 * would do explicit cleanups, but simply running the self-test after hash
743 * computation is more reliable.
744 *
745 * The performance cost of this quick self-test is around 0.6% at the "$2a$08"
746 * setting.
747 */
748 char *__crypt_blowfish(const char *key, const char *setting, char *output)
749 {
750 const char *test_key = "8b \xd0\xc1\xd2\xcf\xcc\xd8";
751 const char *test_setting = "$2a$00$abcdefghijklmnopqrstuu";
752 static const char test_hashes[2][34] = {
753 "i1D709vfamulimlGcq0qq3UvuUasvEa\0\x55", /* 'a', 'b', 'y' */
754 "VUrPmXD6q/nVSSp7pNDhCR9071IfIRe\0\x55", /* 'x' */
755 };
756 const char *test_hash = test_hashes[0];
757 char *retval;
758 const char *p;
759 int ok;
760 struct {
761 char s[7 + 22 + 1];
762 char o[7 + 22 + 31 + 1 + 1 + 1];
763 } buf;
764
765 /* Hash the supplied password */
766 retval = BF_crypt(key, setting, output, 16);
767
768 /*
769 * Do a quick self-test. It is important that we make both calls to BF_crypt()
770 * from the same scope such that they likely use the same stack locations,
771 * which makes the second call overwrite the first call's sensitive data on the
772 * stack and makes it more likely that any alignment related issues would be
773 * detected by the self-test.
774 */
775 memcpy(buf.s, test_setting, sizeof(buf.s));
776 if (retval) {
777 unsigned int flags = flags_by_subtype[setting[2] - 'a'];
778 test_hash = test_hashes[flags & 1];
779 buf.s[2] = setting[2];
780 }
781 memset(buf.o, 0x55, sizeof(buf.o));
782 buf.o[sizeof(buf.o) - 1] = 0;
783 p = BF_crypt(test_key, buf.s, buf.o, 1);
784
785 ok = (p == buf.o &&
786 !memcmp(p, buf.s, 7 + 22) &&
787 !memcmp(p + (7 + 22),
788 test_hash,
789 31 + 1 + 1 + 1));
790
791 {
792 const char *k = "\xff\xa3" "34" "\xff\xff\xff\xa3" "345";
793 BF_key ae, ai, ye, yi;
794 BF_set_key(k, ae, ai, 2); /* $2a$ */
795 BF_set_key(k, ye, yi, 4); /* $2y$ */
796 ai[0] ^= 0x10000; /* undo the safety (for comparison) */
797 ok = ok && ai[0] == 0xdb9c59bc && ye[17] == 0x33343500 &&
798 !memcmp(ae, ye, sizeof(ae)) &&
799 !memcmp(ai, yi, sizeof(ai));
800 }
801
802 if (ok && retval)
803 return retval;
804
805 return "*";
806 }
807