Make JetStream 2
[WebKit-https.git] / PerformanceTests / JetStream2 / worker / bomb-subtests / crypto-aes.js
1 /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -  */
2
3 /*
4  * AES Cipher function: encrypt 'input' with Rijndael algorithm
5  *
6  *   takes   byte-array 'input' (16 bytes)
7  *           2D byte-array key schedule 'w' (Nr+1 x Nb bytes)
8  *
9  *   applies Nr rounds (10/12/14) using key schedule w for 'add round key' stage
10  *
11  *   returns byte-array encrypted value (16 bytes)
12  */
13 function Cipher(input, w) {    // main Cipher function [§5.1]
14   var Nb = 4;               // block size (in words): no of columns in state (fixed at 4 for AES)
15   var Nr = w.length/Nb - 1; // no of rounds: 10/12/14 for 128/192/256-bit keys
16
17   var state = [[],[],[],[]];  // initialise 4xNb byte-array 'state' with input [§3.4]
18   for (var i=0; i<4*Nb; i++) state[i%4][Math.floor(i/4)] = input[i];
19
20   state = AddRoundKey(state, w, 0, Nb);
21
22   for (var round=1; round<Nr; round++) {
23     state = SubBytes(state, Nb);
24     state = ShiftRows(state, Nb);
25     state = MixColumns(state, Nb);
26     state = AddRoundKey(state, w, round, Nb);
27   }
28
29   state = SubBytes(state, Nb);
30   state = ShiftRows(state, Nb);
31   state = AddRoundKey(state, w, Nr, Nb);
32
33   var output = new Array(4*Nb);  // convert state to 1-d array before returning [§3.4]
34   for (var i=0; i<4*Nb; i++) output[i] = state[i%4][Math.floor(i/4)];
35   return output;
36 }
37
38
39 function SubBytes(s, Nb) {    // apply SBox to state S [§5.1.1]
40   for (var r=0; r<4; r++) {
41     for (var c=0; c<Nb; c++) s[r][c] = Sbox[s[r][c]];
42   }
43   return s;
44 }
45
46
47 function ShiftRows(s, Nb) {    // shift row r of state S left by r bytes [§5.1.2]
48   var t = new Array(4);
49   for (var r=1; r<4; r++) {
50     for (var c=0; c<4; c++) t[c] = s[r][(c+r)%Nb];  // shift into temp copy
51     for (var c=0; c<4; c++) s[r][c] = t[c];         // and copy back
52   }          // note that this will work for Nb=4,5,6, but not 7,8 (always 4 for AES):
53   return s;  // see fp.gladman.plus.com/cryptography_technology/rijndael/aes.spec.311.pdf 
54 }
55
56
57 function MixColumns(s, Nb) {   // combine bytes of each col of state S [§5.1.3]
58   for (var c=0; c<4; c++) {
59     var a = new Array(4);  // 'a' is a copy of the current column from 's'
60     var b = new Array(4);  // 'b' is a•{02} in GF(2^8)
61     for (var i=0; i<4; i++) {
62       a[i] = s[i][c];
63       b[i] = s[i][c]&0x80 ? s[i][c]<<1 ^ 0x011b : s[i][c]<<1;
64     }
65     // a[n] ^ b[n] is a•{03} in GF(2^8)
66     s[0][c] = b[0] ^ a[1] ^ b[1] ^ a[2] ^ a[3]; // 2*a0 + 3*a1 + a2 + a3
67     s[1][c] = a[0] ^ b[1] ^ a[2] ^ b[2] ^ a[3]; // a0 * 2*a1 + 3*a2 + a3
68     s[2][c] = a[0] ^ a[1] ^ b[2] ^ a[3] ^ b[3]; // a0 + a1 + 2*a2 + 3*a3
69     s[3][c] = a[0] ^ b[0] ^ a[1] ^ a[2] ^ b[3]; // 3*a0 + a1 + a2 + 2*a3
70   }
71   return s;
72 }
73
74
75 function AddRoundKey(state, w, rnd, Nb) {  // xor Round Key into state S [§5.1.4]
76   for (var r=0; r<4; r++) {
77     for (var c=0; c<Nb; c++) state[r][c] ^= w[rnd*4+c][r];
78   }
79   return state;
80 }
81
82
83 function KeyExpansion(key) {  // generate Key Schedule (byte-array Nr+1 x Nb) from Key [§5.2]
84   var Nb = 4;            // block size (in words): no of columns in state (fixed at 4 for AES)
85   var Nk = key.length/4  // key length (in words): 4/6/8 for 128/192/256-bit keys
86   var Nr = Nk + 6;       // no of rounds: 10/12/14 for 128/192/256-bit keys
87
88   var w = new Array(Nb*(Nr+1));
89   var temp = new Array(4);
90
91   for (var i=0; i<Nk; i++) {
92     var r = [key[4*i], key[4*i+1], key[4*i+2], key[4*i+3]];
93     w[i] = r;
94   }
95
96   for (var i=Nk; i<(Nb*(Nr+1)); i++) {
97     w[i] = new Array(4);
98     for (var t=0; t<4; t++) temp[t] = w[i-1][t];
99     if (i % Nk == 0) {
100       temp = SubWord(RotWord(temp));
101       for (var t=0; t<4; t++) temp[t] ^= Rcon[i/Nk][t];
102     } else if (Nk > 6 && i%Nk == 4) {
103       temp = SubWord(temp);
104     }
105     for (var t=0; t<4; t++) w[i][t] = w[i-Nk][t] ^ temp[t];
106   }
107
108   return w;
109 }
110
111 function SubWord(w) {    // apply SBox to 4-byte word w
112   for (var i=0; i<4; i++) w[i] = Sbox[w[i]];
113   return w;
114 }
115
116 function RotWord(w) {    // rotate 4-byte word w left by one byte
117   w[4] = w[0];
118   for (var i=0; i<4; i++) w[i] = w[i+1];
119   return w;
120 }
121
122
123 // Sbox is pre-computed multiplicative inverse in GF(2^8) used in SubBytes and KeyExpansion [§5.1.1]
124 var Sbox =  [0x63,0x7c,0x77,0x7b,0xf2,0x6b,0x6f,0xc5,0x30,0x01,0x67,0x2b,0xfe,0xd7,0xab,0x76,
125              0xca,0x82,0xc9,0x7d,0xfa,0x59,0x47,0xf0,0xad,0xd4,0xa2,0xaf,0x9c,0xa4,0x72,0xc0,
126              0xb7,0xfd,0x93,0x26,0x36,0x3f,0xf7,0xcc,0x34,0xa5,0xe5,0xf1,0x71,0xd8,0x31,0x15,
127              0x04,0xc7,0x23,0xc3,0x18,0x96,0x05,0x9a,0x07,0x12,0x80,0xe2,0xeb,0x27,0xb2,0x75,
128              0x09,0x83,0x2c,0x1a,0x1b,0x6e,0x5a,0xa0,0x52,0x3b,0xd6,0xb3,0x29,0xe3,0x2f,0x84,
129              0x53,0xd1,0x00,0xed,0x20,0xfc,0xb1,0x5b,0x6a,0xcb,0xbe,0x39,0x4a,0x4c,0x58,0xcf,
130              0xd0,0xef,0xaa,0xfb,0x43,0x4d,0x33,0x85,0x45,0xf9,0x02,0x7f,0x50,0x3c,0x9f,0xa8,
131              0x51,0xa3,0x40,0x8f,0x92,0x9d,0x38,0xf5,0xbc,0xb6,0xda,0x21,0x10,0xff,0xf3,0xd2,
132              0xcd,0x0c,0x13,0xec,0x5f,0x97,0x44,0x17,0xc4,0xa7,0x7e,0x3d,0x64,0x5d,0x19,0x73,
133              0x60,0x81,0x4f,0xdc,0x22,0x2a,0x90,0x88,0x46,0xee,0xb8,0x14,0xde,0x5e,0x0b,0xdb,
134              0xe0,0x32,0x3a,0x0a,0x49,0x06,0x24,0x5c,0xc2,0xd3,0xac,0x62,0x91,0x95,0xe4,0x79,
135              0xe7,0xc8,0x37,0x6d,0x8d,0xd5,0x4e,0xa9,0x6c,0x56,0xf4,0xea,0x65,0x7a,0xae,0x08,
136              0xba,0x78,0x25,0x2e,0x1c,0xa6,0xb4,0xc6,0xe8,0xdd,0x74,0x1f,0x4b,0xbd,0x8b,0x8a,
137              0x70,0x3e,0xb5,0x66,0x48,0x03,0xf6,0x0e,0x61,0x35,0x57,0xb9,0x86,0xc1,0x1d,0x9e,
138              0xe1,0xf8,0x98,0x11,0x69,0xd9,0x8e,0x94,0x9b,0x1e,0x87,0xe9,0xce,0x55,0x28,0xdf,
139              0x8c,0xa1,0x89,0x0d,0xbf,0xe6,0x42,0x68,0x41,0x99,0x2d,0x0f,0xb0,0x54,0xbb,0x16];
140
141 // Rcon is Round Constant used for the Key Expansion [1st col is 2^(r-1) in GF(2^8)] [§5.2]
142 var Rcon = [ [0x00, 0x00, 0x00, 0x00],
143              [0x01, 0x00, 0x00, 0x00],
144              [0x02, 0x00, 0x00, 0x00],
145              [0x04, 0x00, 0x00, 0x00],
146              [0x08, 0x00, 0x00, 0x00],
147              [0x10, 0x00, 0x00, 0x00],
148              [0x20, 0x00, 0x00, 0x00],
149              [0x40, 0x00, 0x00, 0x00],
150              [0x80, 0x00, 0x00, 0x00],
151              [0x1b, 0x00, 0x00, 0x00],
152              [0x36, 0x00, 0x00, 0x00] ]; 
153
154
155 /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -  */
156
157 /* 
158  * Use AES to encrypt 'plaintext' with 'password' using 'nBits' key, in 'Counter' mode of operation
159  *                           - see http://csrc.nist.gov/publications/nistpubs/800-38a/sp800-38a.pdf
160  *   for each block
161  *   - outputblock = cipher(counter, key)
162  *   - cipherblock = plaintext xor outputblock
163  */
164 function AESEncryptCtr(plaintext, password, nBits) {
165   if (!(nBits==128 || nBits==192 || nBits==256)) return '';  // standard allows 128/192/256 bit keys
166
167   // for this example script, generate the key by applying Cipher to 1st 16/24/32 chars of password; 
168   // for real-world applications, a more secure approach would be to hash the password e.g. with SHA-1
169   var nBytes = nBits/8;  // no bytes in key
170   var pwBytes = new Array(nBytes);
171   for (var i=0; i<nBytes; i++) pwBytes[i] = password.charCodeAt(i) & 0xff;
172   var key = Cipher(pwBytes, KeyExpansion(pwBytes));
173   key = key.concat(key.slice(0, nBytes-16));  // key is now 16/24/32 bytes long
174
175   // initialise counter block (NIST SP800-38A §B.2): millisecond time-stamp for nonce in 1st 8 bytes,
176   // block counter in 2nd 8 bytes
177   var blockSize = 16;  // block size fixed at 16 bytes / 128 bits (Nb=4) for AES
178   var counterBlock = new Array(blockSize);  // block size fixed at 16 bytes / 128 bits (Nb=4) for AES
179   var nonce = (new Date()).getTime();  // milliseconds since 1-Jan-1970
180
181   // encode nonce in two stages to cater for JavaScript 32-bit limit on bitwise ops
182   for (var i=0; i<4; i++) counterBlock[i] = (nonce >>> i*8) & 0xff;
183   for (var i=0; i<4; i++) counterBlock[i+4] = (nonce/0x100000000 >>> i*8) & 0xff; 
184
185   // generate key schedule - an expansion of the key into distinct Key Rounds for each round
186   var keySchedule = KeyExpansion(key);
187
188   var blockCount = Math.ceil(plaintext.length/blockSize);
189   var ciphertext = new Array(blockCount);  // ciphertext as array of strings
190   
191   for (var b=0; b<blockCount; b++) {
192     // set counter (block #) in last 8 bytes of counter block (leaving nonce in 1st 8 bytes)
193     // again done in two stages for 32-bit ops
194     for (var c=0; c<4; c++) counterBlock[15-c] = (b >>> c*8) & 0xff;
195     for (var c=0; c<4; c++) counterBlock[15-c-4] = (b/0x100000000 >>> c*8)
196
197     var cipherCntr = Cipher(counterBlock, keySchedule);  // -- encrypt counter block --
198     
199     // calculate length of final block:
200     var blockLength = b<blockCount-1 ? blockSize : (plaintext.length-1)%blockSize+1;
201
202     var ct = '';
203     for (var i=0; i<blockLength; i++) {  // -- xor plaintext with ciphered counter byte-by-byte --
204       var plaintextByte = plaintext.charCodeAt(b*blockSize+i);
205       var cipherByte = plaintextByte ^ cipherCntr[i];
206       ct += String.fromCharCode(cipherByte);
207     }
208     // ct is now ciphertext for this block
209
210     ciphertext[b] = escCtrlChars(ct);  // escape troublesome characters in ciphertext
211   }
212
213   // convert the nonce to a string to go on the front of the ciphertext
214   var ctrTxt = '';
215   for (var i=0; i<8; i++) ctrTxt += String.fromCharCode(counterBlock[i]);
216   ctrTxt = escCtrlChars(ctrTxt);
217
218   // use '-' to separate blocks, use Array.join to concatenate arrays of strings for efficiency
219   return ctrTxt + '-' + ciphertext.join('-');
220 }
221
222
223 /* 
224  * Use AES to decrypt 'ciphertext' with 'password' using 'nBits' key, in Counter mode of operation
225  *
226  *   for each block
227  *   - outputblock = cipher(counter, key)
228  *   - cipherblock = plaintext xor outputblock
229  */
230 function AESDecryptCtr(ciphertext, password, nBits) {
231   if (!(nBits==128 || nBits==192 || nBits==256)) return '';  // standard allows 128/192/256 bit keys
232
233   var nBytes = nBits/8;  // no bytes in key
234   var pwBytes = new Array(nBytes);
235   for (var i=0; i<nBytes; i++) pwBytes[i] = password.charCodeAt(i) & 0xff;
236   var pwKeySchedule = KeyExpansion(pwBytes);
237   var key = Cipher(pwBytes, pwKeySchedule);
238   key = key.concat(key.slice(0, nBytes-16));  // key is now 16/24/32 bytes long
239
240   var keySchedule = KeyExpansion(key);
241
242   ciphertext = ciphertext.split('-');  // split ciphertext into array of block-length strings 
243
244   // recover nonce from 1st element of ciphertext
245   var blockSize = 16;  // block size fixed at 16 bytes / 128 bits (Nb=4) for AES
246   var counterBlock = new Array(blockSize);
247   var ctrTxt = unescCtrlChars(ciphertext[0]);
248   for (var i=0; i<8; i++) counterBlock[i] = ctrTxt.charCodeAt(i);
249
250   var plaintext = new Array(ciphertext.length-1);
251
252   for (var b=1; b<ciphertext.length; b++) {
253     // set counter (block #) in last 8 bytes of counter block (leaving nonce in 1st 8 bytes)
254     for (var c=0; c<4; c++) counterBlock[15-c] = ((b-1) >>> c*8) & 0xff;
255     for (var c=0; c<4; c++) counterBlock[15-c-4] = ((b/0x100000000-1) >>> c*8) & 0xff;
256
257     var cipherCntr = Cipher(counterBlock, keySchedule);  // encrypt counter block
258
259     ciphertext[b] = unescCtrlChars(ciphertext[b]);
260
261     var pt = '';
262     for (var i=0; i<ciphertext[b].length; i++) {
263       // -- xor plaintext with ciphered counter byte-by-byte --
264       var ciphertextByte = ciphertext[b].charCodeAt(i);
265       var plaintextByte = ciphertextByte ^ cipherCntr[i];
266       pt += String.fromCharCode(plaintextByte);
267     }
268     // pt is now plaintext for this block
269
270     plaintext[b-1] = pt;  // b-1 'cos no initial nonce block in plaintext
271   }
272
273   return plaintext.join('');
274 }
275
276 /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -  */
277
278 function escCtrlChars(str) {  // escape control chars which might cause problems handling ciphertext
279   return str.replace(/[\0\t\n\v\f\r\xa0'"!-]/g, function(c) { return '!' + c.charCodeAt(0) + '!'; });
280 }  // \xa0 to cater for bug in Firefox; include '-' to leave it free for use as a block marker
281
282 function unescCtrlChars(str) {  // unescape potentially problematic control characters
283   return str.replace(/!\d\d?\d?!/g, function(c) { return String.fromCharCode(c.slice(1,-1)); });
284 }
285 /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -  */
286
287 /*
288  * if escCtrlChars()/unescCtrlChars() still gives problems, use encodeBase64()/decodeBase64() instead
289  */
290 var b64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=";
291
292 function encodeBase64(str) {  // http://tools.ietf.org/html/rfc4648
293    var o1, o2, o3, h1, h2, h3, h4, bits, i=0, enc='';
294    
295    str = encodeUTF8(str);  // encode multi-byte chars into UTF-8 for byte-array
296
297    do {  // pack three octets into four hexets
298       o1 = str.charCodeAt(i++);
299       o2 = str.charCodeAt(i++);
300       o3 = str.charCodeAt(i++);
301       
302       bits = o1<<16 | o2<<8 | o3;
303       
304       h1 = bits>>18 & 0x3f;
305       h2 = bits>>12 & 0x3f;
306       h3 = bits>>6 & 0x3f;
307       h4 = bits & 0x3f;
308       
309       // end of string? index to '=' in b64
310       if (isNaN(o3)) h4 = 64;
311       if (isNaN(o2)) h3 = 64;
312       
313       // use hexets to index into b64, and append result to encoded string
314       enc += b64.charAt(h1) + b64.charAt(h2) + b64.charAt(h3) + b64.charAt(h4);
315    } while (i < str.length);
316    
317    return enc;
318 }
319
320 function decodeBase64(str) {
321    var o1, o2, o3, h1, h2, h3, h4, bits, i=0, enc='';
322
323    do {  // unpack four hexets into three octets using index points in b64
324       h1 = b64.indexOf(str.charAt(i++));
325       h2 = b64.indexOf(str.charAt(i++));
326       h3 = b64.indexOf(str.charAt(i++));
327       h4 = b64.indexOf(str.charAt(i++));
328       
329       bits = h1<<18 | h2<<12 | h3<<6 | h4;
330       
331       o1 = bits>>16 & 0xff;
332       o2 = bits>>8 & 0xff;
333       o3 = bits & 0xff;
334       
335       if (h3 == 64)      enc += String.fromCharCode(o1);
336       else if (h4 == 64) enc += String.fromCharCode(o1, o2);
337       else               enc += String.fromCharCode(o1, o2, o3);
338    } while (i < str.length);
339
340    return decodeUTF8(enc);  // decode UTF-8 byte-array back to Unicode
341 }
342
343 function encodeUTF8(str) {  // encode multi-byte string into utf-8 multiple single-byte characters 
344   str = str.replace(
345       /[\u0080-\u07ff]/g,  // U+0080 - U+07FF = 2-byte chars
346       function(c) { 
347         var cc = c.charCodeAt(0);
348         return String.fromCharCode(0xc0 | cc>>6, 0x80 | cc&0x3f); }
349     );
350   str = str.replace(
351       /[\u0800-\uffff]/g,  // U+0800 - U+FFFF = 3-byte chars
352       function(c) { 
353         var cc = c.charCodeAt(0); 
354         return String.fromCharCode(0xe0 | cc>>12, 0x80 | cc>>6&0x3F, 0x80 | cc&0x3f); }
355     );
356   return str;
357 }
358
359 function decodeUTF8(str) {  // decode utf-8 encoded string back into multi-byte characters
360   str = str.replace(
361       /[\u00c0-\u00df][\u0080-\u00bf]/g,                 // 2-byte chars
362       function(c) { 
363         var cc = (c.charCodeAt(0)&0x1f)<<6 | c.charCodeAt(1)&0x3f;
364         return String.fromCharCode(cc); }
365     );
366   str = str.replace(
367       /[\u00e0-\u00ef][\u0080-\u00bf][\u0080-\u00bf]/g,  // 3-byte chars
368       function(c) { 
369         var cc = (c.charCodeAt(0)&0x0f)<<12 | (c.charCodeAt(1)&0x3f<<6) | c.charCodeAt(2)&0x3f; 
370         return String.fromCharCode(cc); }
371     );
372   return str;
373 }
374
375
376 function byteArrayToHexStr(b) {  // convert byte array to hex string for displaying test vectors
377   var s = '';
378   for (var i=0; i<b.length; i++) s += b[i].toString(16) + ' ';
379   return s;
380 }
381
382 /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -  */
383
384
385 var plainText = "ROMEO: But, soft! what light through yonder window breaks?\n\
386 It is the east, and Juliet is the sun.\n\
387 Arise, fair sun, and kill the envious moon,\n\
388 Who is already sick and pale with grief,\n\
389 That thou her maid art far more fair than she:\n\
390 Be not her maid, since she is envious;\n\
391 Her vestal livery is but sick and green\n\
392 And none but fools do wear it; cast it off.\n\
393 It is my lady, O, it is my love!\n\
394 O, that she knew she were!\n\
395 She speaks yet she says nothing: what of that?\n\
396 Her eye discourses; I will answer it.\n\
397 I am too bold, 'tis not to me she speaks:\n\
398 Two of the fairest stars in all the heaven,\n\
399 Having some business, do entreat her eyes\n\
400 To twinkle in their spheres till they return.\n\
401 What if her eyes were there, they in her head?\n\
402 The brightness of her cheek would shame those stars,\n\
403 As daylight doth a lamp; her eyes in heaven\n\
404 Would through the airy region stream so bright\n\
405 That birds would sing and think it were not night.\n\
406 See, how she leans her cheek upon her hand!\n\
407 O, that I were a glove upon that hand,\n\
408 That I might touch that cheek!\n\
409 JULIET: Ay me!\n\
410 ROMEO: She speaks:\n\
411 O, speak again, bright angel! for thou art\n\
412 As glorious to this night, being o'er my head\n\
413 As is a winged messenger of heaven\n\
414 Unto the white-upturned wondering eyes\n\
415 Of mortals that fall back to gaze on him\n\
416 When he bestrides the lazy-pacing clouds\n\
417 And sails upon the bosom of the air.";
418
419 var password = "O Romeo, Romeo! wherefore art thou Romeo?";
420
421 var cipherText = AESEncryptCtr(plainText, password, 256);
422 var decryptedText = AESDecryptCtr(cipherText, password, 256);
423
424 if (decryptedText != plainText)
425     throw "ERROR: bad result: expected " + plainText + " but got " + decryptedText;
426
427 postMessage("done");
428 close();