/* * Crack RC4 keys on the Cell's SPUs * H D Moore * */ /* [ Benchmarks ] (jc-wepcrack) 1.25 GHz G4 150,000/sec 3.60 GHz P4 300,000/sec 15 3.6GHz P4 4,500,000/sec (pico-wepcrack) LX25 2,000,000/sec (~$500 dev kit from http://www.em.avnet.com/) FX60 5,000,000/sec (~$2500 dev kit from http://www.em.avnet.com/) 15 Cluster 30,000,000/sec (cbe-client) 1 SPU 3.2Ghz 241,000/sec (~$500 PlayStation 3 from ... eBay?) 6 SPU 3.2ghz 1,446,000/sec (~$500 PlayStation 3 from ... eBay?) */ #include #include #include "spe.h" /* waits for dma operations on the specified tag to complete */ static inline void wait_xfer(unsigned int tag) { unsigned int tag_mask = 1 << tag; spu_writech(MFC_WrTagMask, tag_mask); spu_mfcstat(MFC_TAG_UPDATE_ALL); } /* writes a message to the PPE (blocks if queue is full) */ static inline void write_mbox(unsigned int val) { spu_writech(SPU_WrOutMbox, val); } /* reads a message from the PPE (blocks if queue is empty) */ static inline unsigned int read_mbox(void) { return spu_readch(SPU_RdInMbox); } /* start state for RC4 KSA */ unsigned int new_state[256]; unsigned int new_index1, new_index2; #define swap_byte(x,y) t = *(x); *(x) = *(y); *(y) = t /* This routine is the meat of our processing time */ #define RC4_KSA_OLD(n) \ { \ index2 = (key_buf[index1] + state[(n)] + index2) & 0xff; \ if (++index1 == key_len) index1 = 0; \ swap_byte(&state[(n)], &state[index2]); \ } /* This routine is the meat of our processing time */ #define RC4_KSA(n, o) \ { \ index2 = (key_buf[(o)] + state[(n)] + index2) & 0xff; \ swap_byte(&state[(n)], &state[index2]); \ } #define RC4_BYTE(n) \ { \ x = (x + 1) & 0xff; \ y = (state[x] + y) & 0xff; \ swap_byte(&state[x], &state[y]); \ index1 = (state[x] + state[y]) & 0xff; \ txt_buf[(n)] ^= state[index1]; \ } void inline rc4_init(wepcrack_job_t *job, unsigned char *key_buf) { unsigned int index1 = 0, index2 = 0; unsigned int i, t; unsigned int *state = new_state; unsigned int key_len; key_len = job->keysize; for(i=0; i<256; i++) state[i] = i; /* precalculate for the static IV */ RC4_KSA(0, 0); RC4_KSA(1, 1); RC4_KSA(2, 2); new_index1 = index1; new_index2 = index2; } static inline int rc4(wepcrack_job_t *job, unsigned char *key_buf) { unsigned char *txt_buf; unsigned int key_len; unsigned int x = 0, y = 0, t; unsigned int index1 = new_index1, index2 = new_index2; unsigned int state[256]; uint64_t prga = 0; /* initialize the state */ memcpy(state, new_state, sizeof(state)); txt_buf = (unsigned char *)&prga; key_len = job->keysize; /* fast and ugly */ RC4_KSA(3, 3); RC4_KSA(4, 4); RC4_KSA(5, 5); RC4_KSA(6, 6); RC4_KSA(7, 7); if (key_len == 8) { RC4_KSA(8, 0); RC4_KSA(9, 1); RC4_KSA(10, 2); RC4_KSA(11, 3); RC4_KSA(12, 4); RC4_KSA(13, 5); RC4_KSA(14, 6); RC4_KSA(15, 7); RC4_KSA(16, 0); RC4_KSA(17, 1); RC4_KSA(18, 2); RC4_KSA(19, 3); RC4_KSA(20, 4); RC4_KSA(21, 5); RC4_KSA(22, 6); RC4_KSA(23, 7); RC4_KSA(24, 0); RC4_KSA(25, 1); RC4_KSA(26, 2); RC4_KSA(27, 3); RC4_KSA(28, 4); RC4_KSA(29, 5); RC4_KSA(30, 6); RC4_KSA(31, 7); RC4_KSA(32, 0); RC4_KSA(33, 1); RC4_KSA(34, 2); RC4_KSA(35, 3); RC4_KSA(36, 4); RC4_KSA(37, 5); RC4_KSA(38, 6); RC4_KSA(39, 7); RC4_KSA(40, 0); RC4_KSA(41, 1); RC4_KSA(42, 2); RC4_KSA(43, 3); RC4_KSA(44, 4); RC4_KSA(45, 5); RC4_KSA(46, 6); RC4_KSA(47, 7); RC4_KSA(48, 0); RC4_KSA(49, 1); RC4_KSA(50, 2); RC4_KSA(51, 3); RC4_KSA(52, 4); RC4_KSA(53, 5); RC4_KSA(54, 6); RC4_KSA(55, 7); RC4_KSA(56, 0); RC4_KSA(57, 1); RC4_KSA(58, 2); RC4_KSA(59, 3); RC4_KSA(60, 4); RC4_KSA(61, 5); RC4_KSA(62, 6); RC4_KSA(63, 7); RC4_KSA(64, 0); RC4_KSA(65, 1); RC4_KSA(66, 2); RC4_KSA(67, 3); RC4_KSA(68, 4); RC4_KSA(69, 5); RC4_KSA(70, 6); RC4_KSA(71, 7); RC4_KSA(72, 0); RC4_KSA(73, 1); RC4_KSA(74, 2); RC4_KSA(75, 3); RC4_KSA(76, 4); RC4_KSA(77, 5); RC4_KSA(78, 6); RC4_KSA(79, 7); RC4_KSA(80, 0); RC4_KSA(81, 1); RC4_KSA(82, 2); RC4_KSA(83, 3); RC4_KSA(84, 4); RC4_KSA(85, 5); RC4_KSA(86, 6); RC4_KSA(87, 7); RC4_KSA(88, 0); RC4_KSA(89, 1); RC4_KSA(90, 2); RC4_KSA(91, 3); RC4_KSA(92, 4); RC4_KSA(93, 5); RC4_KSA(94, 6); RC4_KSA(95, 7); RC4_KSA(96, 0); RC4_KSA(97, 1); RC4_KSA(98, 2); RC4_KSA(99, 3); RC4_KSA(100, 4); RC4_KSA(101, 5); RC4_KSA(102, 6); RC4_KSA(103, 7); RC4_KSA(104, 0); RC4_KSA(105, 1); RC4_KSA(106, 2); RC4_KSA(107, 3); RC4_KSA(108, 4); RC4_KSA(109, 5); RC4_KSA(110, 6); RC4_KSA(111, 7); RC4_KSA(112, 0); RC4_KSA(113, 1); RC4_KSA(114, 2); RC4_KSA(115, 3); RC4_KSA(116, 4); RC4_KSA(117, 5); RC4_KSA(118, 6); RC4_KSA(119, 7); RC4_KSA(120, 0); RC4_KSA(121, 1); RC4_KSA(122, 2); RC4_KSA(123, 3); RC4_KSA(124, 4); RC4_KSA(125, 5); RC4_KSA(126, 6); RC4_KSA(127, 7); RC4_KSA(128, 0); RC4_KSA(129, 1); RC4_KSA(130, 2); RC4_KSA(131, 3); RC4_KSA(132, 4); RC4_KSA(133, 5); RC4_KSA(134, 6); RC4_KSA(135, 7); RC4_KSA(136, 0); RC4_KSA(137, 1); RC4_KSA(138, 2); RC4_KSA(139, 3); RC4_KSA(140, 4); RC4_KSA(141, 5); RC4_KSA(142, 6); RC4_KSA(143, 7); RC4_KSA(144, 0); RC4_KSA(145, 1); RC4_KSA(146, 2); RC4_KSA(147, 3); RC4_KSA(148, 4); RC4_KSA(149, 5); RC4_KSA(150, 6); RC4_KSA(151, 7); RC4_KSA(152, 0); RC4_KSA(153, 1); RC4_KSA(154, 2); RC4_KSA(155, 3); RC4_KSA(156, 4); RC4_KSA(157, 5); RC4_KSA(158, 6); RC4_KSA(159, 7); RC4_KSA(160, 0); RC4_KSA(161, 1); RC4_KSA(162, 2); RC4_KSA(163, 3); RC4_KSA(164, 4); RC4_KSA(165, 5); RC4_KSA(166, 6); RC4_KSA(167, 7); RC4_KSA(168, 0); RC4_KSA(169, 1); RC4_KSA(170, 2); RC4_KSA(171, 3); RC4_KSA(172, 4); RC4_KSA(173, 5); RC4_KSA(174, 6); RC4_KSA(175, 7); RC4_KSA(176, 0); RC4_KSA(177, 1); RC4_KSA(178, 2); RC4_KSA(179, 3); RC4_KSA(180, 4); RC4_KSA(181, 5); RC4_KSA(182, 6); RC4_KSA(183, 7); RC4_KSA(184, 0); RC4_KSA(185, 1); RC4_KSA(186, 2); RC4_KSA(187, 3); RC4_KSA(188, 4); RC4_KSA(189, 5); RC4_KSA(190, 6); RC4_KSA(191, 7); RC4_KSA(192, 0); RC4_KSA(193, 1); RC4_KSA(194, 2); RC4_KSA(195, 3); RC4_KSA(196, 4); RC4_KSA(197, 5); RC4_KSA(198, 6); RC4_KSA(199, 7); RC4_KSA(200, 0); RC4_KSA(201, 1); RC4_KSA(202, 2); RC4_KSA(203, 3); RC4_KSA(204, 4); RC4_KSA(205, 5); RC4_KSA(206, 6); RC4_KSA(207, 7); RC4_KSA(208, 0); RC4_KSA(209, 1); RC4_KSA(210, 2); RC4_KSA(211, 3); RC4_KSA(212, 4); RC4_KSA(213, 5); RC4_KSA(214, 6); RC4_KSA(215, 7); RC4_KSA(216, 0); RC4_KSA(217, 1); RC4_KSA(218, 2); RC4_KSA(219, 3); RC4_KSA(220, 4); RC4_KSA(221, 5); RC4_KSA(222, 6); RC4_KSA(223, 7); RC4_KSA(224, 0); RC4_KSA(225, 1); RC4_KSA(226, 2); RC4_KSA(227, 3); RC4_KSA(228, 4); RC4_KSA(229, 5); RC4_KSA(230, 6); RC4_KSA(231, 7); RC4_KSA(232, 0); RC4_KSA(233, 1); RC4_KSA(234, 2); RC4_KSA(235, 3); RC4_KSA(236, 4); RC4_KSA(237, 5); RC4_KSA(238, 6); RC4_KSA(239, 7); RC4_KSA(240, 0); RC4_KSA(241, 1); RC4_KSA(242, 2); RC4_KSA(243, 3); RC4_KSA(244, 4); RC4_KSA(245, 5); RC4_KSA(246, 6); RC4_KSA(247, 7); RC4_KSA(248, 0); RC4_KSA(249, 1); RC4_KSA(250, 2); RC4_KSA(251, 3); RC4_KSA(252, 4); RC4_KSA(253, 5); RC4_KSA(254, 6); RC4_KSA(255, 7); } else { RC4_KSA(8, 8); RC4_KSA(9, 9); RC4_KSA(10, 10); RC4_KSA(11, 11); RC4_KSA(12, 12); RC4_KSA(13, 13); RC4_KSA(14, 14); RC4_KSA(15, 15); RC4_KSA(16, 0); RC4_KSA(17, 1); RC4_KSA(18, 2); RC4_KSA(19, 3); RC4_KSA(20, 4); RC4_KSA(21, 5); RC4_KSA(22, 6); RC4_KSA(23, 7); RC4_KSA(24, 8); RC4_KSA(25, 9); RC4_KSA(26, 10); RC4_KSA(27, 11); RC4_KSA(28, 12); RC4_KSA(29, 13); RC4_KSA(30, 14); RC4_KSA(31, 15); RC4_KSA(32, 0); RC4_KSA(33, 1); RC4_KSA(34, 2); RC4_KSA(35, 3); RC4_KSA(36, 4); RC4_KSA(37, 5); RC4_KSA(38, 6); RC4_KSA(39, 7); RC4_KSA(40, 8); RC4_KSA(41, 9); RC4_KSA(42, 10); RC4_KSA(43, 11); RC4_KSA(44, 12); RC4_KSA(45, 13); RC4_KSA(46, 14); RC4_KSA(47, 15); RC4_KSA(48, 0); RC4_KSA(49, 1); RC4_KSA(50, 2); RC4_KSA(51, 3); RC4_KSA(52, 4); RC4_KSA(53, 5); RC4_KSA(54, 6); RC4_KSA(55, 7); RC4_KSA(56, 8); RC4_KSA(57, 9); RC4_KSA(58, 10); RC4_KSA(59, 11); RC4_KSA(60, 12); RC4_KSA(61, 13); RC4_KSA(62, 14); RC4_KSA(63, 15); RC4_KSA(64, 0); RC4_KSA(65, 1); RC4_KSA(66, 2); RC4_KSA(67, 3); RC4_KSA(68, 4); RC4_KSA(69, 5); RC4_KSA(70, 6); RC4_KSA(71, 7); RC4_KSA(72, 8); RC4_KSA(73, 9); RC4_KSA(74, 10); RC4_KSA(75, 11); RC4_KSA(76, 12); RC4_KSA(77, 13); RC4_KSA(78, 14); RC4_KSA(79, 15); RC4_KSA(80, 0); RC4_KSA(81, 1); RC4_KSA(82, 2); RC4_KSA(83, 3); RC4_KSA(84, 4); RC4_KSA(85, 5); RC4_KSA(86, 6); RC4_KSA(87, 7); RC4_KSA(88, 8); RC4_KSA(89, 9); RC4_KSA(90, 10); RC4_KSA(91, 11); RC4_KSA(92, 12); RC4_KSA(93, 13); RC4_KSA(94, 14); RC4_KSA(95, 15); RC4_KSA(96, 0); RC4_KSA(97, 1); RC4_KSA(98, 2); RC4_KSA(99, 3); RC4_KSA(100, 4); RC4_KSA(101, 5); RC4_KSA(102, 6); RC4_KSA(103, 7); RC4_KSA(104, 8); RC4_KSA(105, 9); RC4_KSA(106, 10); RC4_KSA(107, 11); RC4_KSA(108, 12); RC4_KSA(109, 13); RC4_KSA(110, 14); RC4_KSA(111, 15); RC4_KSA(112, 0); RC4_KSA(113, 1); RC4_KSA(114, 2); RC4_KSA(115, 3); RC4_KSA(116, 4); RC4_KSA(117, 5); RC4_KSA(118, 6); RC4_KSA(119, 7); RC4_KSA(120, 8); RC4_KSA(121, 9); RC4_KSA(122, 10); RC4_KSA(123, 11); RC4_KSA(124, 12); RC4_KSA(125, 13); RC4_KSA(126, 14); RC4_KSA(127, 15); RC4_KSA(128, 0); RC4_KSA(129, 1); RC4_KSA(130, 2); RC4_KSA(131, 3); RC4_KSA(132, 4); RC4_KSA(133, 5); RC4_KSA(134, 6); RC4_KSA(135, 7); RC4_KSA(136, 8); RC4_KSA(137, 9); RC4_KSA(138, 10); RC4_KSA(139, 11); RC4_KSA(140, 12); RC4_KSA(141, 13); RC4_KSA(142, 14); RC4_KSA(143, 15); RC4_KSA(144, 0); RC4_KSA(145, 1); RC4_KSA(146, 2); RC4_KSA(147, 3); RC4_KSA(148, 4); RC4_KSA(149, 5); RC4_KSA(150, 6); RC4_KSA(151, 7); RC4_KSA(152, 8); RC4_KSA(153, 9); RC4_KSA(154, 10); RC4_KSA(155, 11); RC4_KSA(156, 12); RC4_KSA(157, 13); RC4_KSA(158, 14); RC4_KSA(159, 15); RC4_KSA(160, 0); RC4_KSA(161, 1); RC4_KSA(162, 2); RC4_KSA(163, 3); RC4_KSA(164, 4); RC4_KSA(165, 5); RC4_KSA(166, 6); RC4_KSA(167, 7); RC4_KSA(168, 8); RC4_KSA(169, 9); RC4_KSA(170, 10); RC4_KSA(171, 11); RC4_KSA(172, 12); RC4_KSA(173, 13); RC4_KSA(174, 14); RC4_KSA(175, 15); RC4_KSA(176, 0); RC4_KSA(177, 1); RC4_KSA(178, 2); RC4_KSA(179, 3); RC4_KSA(180, 4); RC4_KSA(181, 5); RC4_KSA(182, 6); RC4_KSA(183, 7); RC4_KSA(184, 8); RC4_KSA(185, 9); RC4_KSA(186, 10); RC4_KSA(187, 11); RC4_KSA(188, 12); RC4_KSA(189, 13); RC4_KSA(190, 14); RC4_KSA(191, 15); RC4_KSA(192, 0); RC4_KSA(193, 1); RC4_KSA(194, 2); RC4_KSA(195, 3); RC4_KSA(196, 4); RC4_KSA(197, 5); RC4_KSA(198, 6); RC4_KSA(199, 7); RC4_KSA(200, 8); RC4_KSA(201, 9); RC4_KSA(202, 10); RC4_KSA(203, 11); RC4_KSA(204, 12); RC4_KSA(205, 13); RC4_KSA(206, 14); RC4_KSA(207, 15); RC4_KSA(208, 0); RC4_KSA(209, 1); RC4_KSA(210, 2); RC4_KSA(211, 3); RC4_KSA(212, 4); RC4_KSA(213, 5); RC4_KSA(214, 6); RC4_KSA(215, 7); RC4_KSA(216, 8); RC4_KSA(217, 9); RC4_KSA(218, 10); RC4_KSA(219, 11); RC4_KSA(220, 12); RC4_KSA(221, 13); RC4_KSA(222, 14); RC4_KSA(223, 15); RC4_KSA(224, 0); RC4_KSA(225, 1); RC4_KSA(226, 2); RC4_KSA(227, 3); RC4_KSA(228, 4); RC4_KSA(229, 5); RC4_KSA(230, 6); RC4_KSA(231, 7); RC4_KSA(232, 8); RC4_KSA(233, 9); RC4_KSA(234, 10); RC4_KSA(235, 11); RC4_KSA(236, 12); RC4_KSA(237, 13); RC4_KSA(238, 14); RC4_KSA(239, 15); RC4_KSA(240, 0); RC4_KSA(241, 1); RC4_KSA(242, 2); RC4_KSA(243, 3); RC4_KSA(244, 4); RC4_KSA(245, 5); RC4_KSA(246, 6); RC4_KSA(247, 7); RC4_KSA(248, 8); RC4_KSA(249, 9); RC4_KSA(250, 10); RC4_KSA(251, 11); RC4_KSA(252, 12); RC4_KSA(253, 13); RC4_KSA(254, 14); RC4_KSA(255, 15); } RC4_BYTE(0); RC4_BYTE(1); RC4_BYTE(2); RC4_BYTE(3); RC4_BYTE(4); RC4_BYTE(5); if ( prga == job->prga_to_match ) { return 1; } else { return 0; } } static inline int crack_rc4(unsigned long long argp, wepcrack_job_t *job, unsigned char *key) { int cracked = 0; uint32_t msg; cracked = rc4(job, key); if (cracked) { /* dma the current key back into main memory */ mfc_put(job, argp, sizeof(wepcrack_job_t), 1, 0, 0); wait_xfer(1); /* tell the ppu that we have a match */ write_mbox(EVENT_CRACK); /* wait for a response from the ppu */ msg = read_mbox(); switch(msg) { case EVENT_CONT: return 0; break; case EVENT_STOP: job->status = JOB_STOP; return 1; break; case EVENT_CRACK: return 1; break; default: break; } /* this could be a match */ return 1; } return 0; } int main (unsigned long long spe_id, unsigned long long argp, unsigned long long envp) { int tag, cracked; wepcrack_job_t job; uint64_t ckey_hi, stop_hi; uint64_t ckey_lo, stop_lo; uint32_t msg; unsigned char *key; /* initial tag */ tag = 1; /* master loop */ while(1) { /* dma the job data and sync */ mfc_get(&job, argp, sizeof(job), tag, 0 ,0); wait_xfer(tag); /* print out what job we got */ fprintf(stderr, "SPU-%llx received job %llu for key size %llu\n", spe_id, job.job, job.keysize); /* initialize our rc4 state for this job */ if (job.keysize == 8) { key = (unsigned char *)&job.curr_key_lo; rc4_init(&job, (unsigned char *)&job.start_key_lo); } else { key = (unsigned char *)&job.curr_key_hi; rc4_init(&job, (unsigned char *)&job.start_key_hi); } job.status = JOB_RUN; cracked = 0; ckey_hi = job.start_key_hi; ckey_lo = job.start_key_lo; stop_hi = job.stop_key_hi; stop_lo = job.stop_key_lo; for(; ckey_hi < stop_hi; ckey_hi++) { job.curr_key_hi = ckey_hi; for(; ckey_lo + 1 != 0; ckey_lo++) { job.curr_key_lo = ckey_lo; if(crack_rc4(argp, &job, key)){ cracked++; break; } } if (cracked) break; } job.curr_key_hi = ckey_hi; if (! cracked) { for(; ckey_lo <= stop_lo; ckey_lo++) { job.curr_key_lo = ckey_lo; if(crack_rc4(argp, &job, key)){ cracked++; break; } } } /* exit if we cracked the key */ if(cracked) break; /* ask the ppu for another key slice */ write_mbox(EVENT_DONE); /* wait for a response from the ppu */ msg = read_mbox(); switch(msg) { case EVENT_STOP: return(1); break; case EVENT_START: case EVENT_CONT: default: break; } /* start the whole process over again */ } /* master loop */ return(0); }