Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(357)

Issues Search
    My Issues | Starred     Open | Closed | All

Side by Side Diff: fusl/src/crypt/crypt_blowfish.c

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

Powered by Google App Engine
This is Rietveld 408576698