API tools faq
paste
Guest User

Untitled

a guest
Jul 20th, 2018
85
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 12.26 KB | None | 0 0
raw download clone embed print report
  1. #include <stdio.h>
  2. #include <stdint.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5. #include <time.h>
  6. #include <stdbool.h>
  7.  
  8. bool debug;
  9. uint8_t *hex = NULL;
  10. uint8_t *currentHash = NULL;
  11. uint8_t *workingHash = NULL;
  12. int workingHashMaxSize;
  13.  
  14. void debug_messages();
  15. void exercise_messages();
  16. void setCurrentHash (uint8_t *msg, int size);
  17. void bruteforce_messages();
  18. void print (uint8_t *old);
  19. void print_s (uint8_t *old, int size);
  20. void bruteNext (uint8_t *old, int cnt);
  21. void brute();
  22. bool compare (uint8_t *newHash, int cnt);
  23. void hashAndPrint (uint8_t *msg, int size);
  24. uint8_t* hash (uint8_t *msg, int size);
  25. uint8_t* block (int blockID, uint8_t *xi, uint8_t *Hi);
  26.  
  27. /*
  28. * Prints solutions to the debug questions given on the walk through
  29. * Select debug = true for extended output.
  30. */
  31. void debug_messages() {
  32. int size;
  33. printf("\nDebug Message i\n");
  34. uint8_t msg1[] = {0xC,0x5,0x4,0xF,0xF,0xD,0xD,0xF};
  35. size = sizeof(msg1)/sizeof(uint8_t);
  36. hashAndPrint(msg1,size);
  37. printf("\nDebug Message ii\n");
  38. uint8_t msg2[] = {0xF,0x9,0x9,0xD,0xE,0xE,0x7,0x9};
  39. size = sizeof(msg2)/sizeof(uint8_t);
  40. hashAndPrint(msg2,size);
  41. printf("\nDebug Message iii\n");
  42. uint8_t msg3[] = {0xA,0x0,0x2,0x8,0xE,0xA,0x0,0xE,0x0,0xC,0x8,0xC,0xC,0x7,0xA,0x6,0x4,0x3,0x0,0x7,0xD,0x4,0x6,0x2,0xB,0xE,0xC,0xC};
  43. size = sizeof(msg3)/sizeof(uint8_t);
  44. hashAndPrint(msg3,size);
  45. printf("\nDebug Message iv\n");
  46. uint8_t msg4[] = {0xC,0xF,0xA,0xE,0x5,0xC,0x6,0xB,0x4,0xA,0xF,0xA,0x3,0xC,0xC,0x8,0x2,0x4,0x7,0xE,0x0,0x9,0x8,0xC,0x6,0x8,0x3,0xD};
  47. size = sizeof(msg4)/sizeof(uint8_t);
  48. hashAndPrint(msg4,size);
  49. }
  50.  
  51. /*
  52. * Prints solutions to the exercise questions given in the handout
  53. * Select debug = true for extended output.
  54. */
  55. void exercise_messages() {
  56. int size;
  57.  
  58. printf("\nMessage i\n");
  59. //0xFAB17E668145A9BCC783BFEE70013522734
  60. uint8_t msg1[] = {0xF,0xA,0xB,0x1,0x7,0xE,0x6,0x6,0x8,0x1,0x4,0x5,0xA,0x9,0xB,0xC,0xC,0x7,0x8,0x3,0xB,0xF,0xE,0xE,0x7,0x0,0x0,0x1,0x3,0x5,0x2,0x2,0x7,0x3,0x4};
  61. size = sizeof(msg1)/sizeof(uint8_t);
  62. hashAndPrint(msg1,size);
  63.  
  64. printf("\nMessage ii\n");
  65. //0xFAB17E668145A9BCC783BFEE70013521912
  66. uint8_t msg2[] = {0xF,0xA,0xB,0x1,0x7,0xE,0x6,0x6,0x8,0x1,0x4,0x5,0xA,0x9,0xB,0xC,0xC,0x7,0x8,0x3,0xB,0xF,0xE,0xE,0x7,0x0,0x0,0x1,0x3,0x5,0x2,0x1,0x9,0x1,0x2};
  67. size = sizeof(msg2)/sizeof(uint8_t);
  68. hashAndPrint(msg2,size);
  69.  
  70. printf("\nMessage iii\n");
  71. //0xEAB17E668145A9BCC783BFEE70013521558
  72. uint8_t msg3[] = {0xE,0xA,0xB,0x1,0x7,0xE,0x6,0x6,0x8,0x1,0x4,0x5,0xA,0x9,0xB,0xC,0xC,0x7,0x8,0x3,0xB,0xF,0xE,0xE,0x7,0x0,0x0,0x1,0x3,0x5,0x2,0x1,0x5,0x5,0x8};
  73. size = sizeof(msg3)/sizeof(uint8_t);
  74. hashAndPrint(msg3,size);
  75.  
  76. printf("\nMessage iv\n");
  77. //0x24A7B9FD294AFE569BB23197FFEAB67D
  78. uint8_t msg4[] = {0x2,0x4,0xA,0x7,0xB,0x9,0xF,0xD,0x2,0x9,0x4,0xA,0xF,0xE,0x5,0x6,0x9,0xB,0xB,0x2,0x3,0x1,0x9,0x7,0xF,0xF,0xE,0xA,0xB,0x6,0x7,0xD};
  79. size = sizeof(msg4)/sizeof(uint8_t);
  80. hashAndPrint(msg4,size);
  81. }
  82.  
  83. void setCurrentHash (uint8_t *msg, int size) {
  84. printf("Searching for this Hash: \n");
  85. currentHash = msg;
  86. print(currentHash);
  87. }
  88.  
  89. /*
  90. * Prints collisions found for brute force question
  91. * Select debug = true for extended output.
  92. */
  93. void bruteforce_messages() {
  94. clock_t start_h=clock();
  95. printf("\nBegin Brute Force i\n");
  96. //uint8_t bmsg1[] = {0xA,0xB,0xC,0xD,0xE,0xF,0x1,0x2,0x3,0x4};
  97. uint8_t bmsg1[] = {0xC,0x5,0x4,0xF,0xF,0xD,0xD,0xF};
  98. uint8_t *hsh = hash(bmsg1, 8);
  99. print(hsh);
  100. setCurrentHash(hsh,5);
  101. brute();
  102. free(hsh);
  103. clock_t end_h = clock();
  104. double time_h = (double)(end_h-start_h)/CLOCKS_PER_SEC;
  105. printf("Brute Force speed %f \n", time_h);
  106. }
  107.  
  108. /*
  109. * Prints out a given hash
  110. * Assumes hash size is 5
  111. */
  112. void print (uint8_t *old) {
  113. int size = 5;
  114. for (int i = 0; i < size; i++) {
  115. printf("%#x\n", old[i]);
  116. }
  117. }
  118.  
  119. /*
  120. * Prints out a given hash
  121. * does not assume size
  122. */
  123. void print_s (uint8_t *old, int size) {
  124. for (int i = 0; i < size; i++) {
  125. printf("%#x\n", old[i]);
  126. }
  127. }
  128.  
  129. /*
  130. * Will recursively brute force the next message
  131. * Check workingHashMaxSize for the maximum size the message can be
  132. */
  133. void bruteNext (uint8_t *old, int cnt) {
  134.  
  135. cnt += 1;
  136.  
  137. uint8_t *hsh = hash(old, cnt);
  138.  
  139. if (compare(hsh,5) == true) {
  140. printf("found collision\n");
  141. print_s(old, cnt);
  142. printf("for hash\n");
  143. print(hsh);
  144. }
  145.  
  146. free(hsh);
  147.  
  148. if (cnt < workingHashMaxSize) {
  149. for (int i = 0; i < 16; i++) {
  150. old[cnt] = hex[i];
  151. bruteNext(old,cnt);
  152. }
  153. } else {
  154. //free(old);
  155. }
  156. }
  157.  
  158. /*
  159. * Call this method to brute force new messages
  160. * This method calls bruteNext recursively.
  161. */
  162. void brute() {
  163. int count = 0;
  164. // Initially give the working hash capacity for 80 bits
  165. // Each element in the array has 4 bits masked
  166. // Effectively 40 bits of working data
  167. workingHashMaxSize = 10;
  168. workingHash = (uint8_t *)malloc(10);
  169. for (int i = 0; i < 16; i++) {
  170. workingHash[0] = hex[i];
  171. bruteNext(workingHash,count);
  172. count = 0;
  173. }
  174. free(workingHash);
  175. }
  176.  
  177. /*
  178. * Compares the generated hash with the hashes we're looking for
  179. * Used when looking for possible collisions
  180. */
  181. bool compare (uint8_t *newHash, int cnt) {
  182. int size = cnt;
  183. bool ok = true;
  184. for ( int i = 0; i < size; i++ ) {
  185. if ( newHash[i] == currentHash[i] ) {
  186. // Looks good!
  187. } else {
  188. ok = false;
  189. break;
  190. }
  191. }
  192. return ok;
  193. }
  194.  
  195. /*
  196. * This method is used for printing out the final hash value of a message
  197. * Useful when debug = false
  198. */
  199. void hashAndPrint (uint8_t *msg, int size) {
  200. uint8_t *msg_r = NULL;;
  201. msg_r = (uint8_t *)malloc(size * sizeof(uint8_t));
  202. memcpy (msg_r,msg,size);
  203. uint8_t *hsh = hash(msg_r, size);
  204. print(hsh);
  205. // Free memory on the heap
  206. free(hsh);
  207. free(msg_r);
  208. }
  209.  
  210. /*
  211. * Hash will first break the message into blocks of 4 bit, and append any nessisary padding
  212. * It will call the block method when hashing each 4 bit block
  213. * Finally, it will then combine the blocks to produce the final hash.
  214. */
  215. uint8_t* hash (uint8_t* msg, int size) {
  216. // if (debug == true) { clock_t start_h=clock(); }
  217.  
  218. //print_s(msg, size);
  219.  
  220. uint8_t *msg_r = NULL;;
  221. int toAppend = 0;
  222. // Check to see if message is correct size
  223. if ( size >= 1 ) {
  224. if (debug == true) { printf("Message size = %d\n", size); }
  225. if ( size%5 != 0 ) {
  226. if (debug == true) { printf("!!! ERROR !!! size of Message is falset 20 bit blocks\n"); }
  227. while (size%5 != 0) {
  228. size += 1;
  229. toAppend += 1;
  230. }
  231. } else {
  232. if (debug == true) { printf("Size of Message is in 20 bit blocks: OK\n"); }
  233. }
  234. } else {
  235. if (debug == true) { printf("!!! FAIL !!! size of message is Zero\n"); }
  236. }
  237.  
  238. if ( toAppend > 0 ) {
  239. // Allocate storage for the new size
  240. msg_r = (uint8_t *)malloc(size * sizeof(uint8_t));
  241. // Copy contents
  242. memcpy (msg_r,msg,size-toAppend);
  243.  
  244. while (!(toAppend < 0)) {
  245. // Append 0x0 to elements falset in array
  246. msg_r[size-toAppend] = 0x0;
  247. toAppend -= 1;
  248. if (debug == true) { printf("!!! Attempting to fix !!! appended 0x0 for padding\n"); }
  249. }
  250. } else {
  251. // Just copy contents
  252. msg_r = (uint8_t *)malloc(size * sizeof(uint8_t));
  253. memcpy (msg_r,msg,size);
  254. }
  255.  
  256. int id = 0;
  257. uint8_t *nextBlock = NULL;
  258. uint8_t blck[5];
  259.  
  260. for ( int i = 0; i < size; i+=5) {
  261. for ( int u = 0; u < 5; u++) {
  262. blck[u] = msg_r[i+u];
  263. }
  264.  
  265. id += 1;
  266. if ( i == 0 ) {
  267. if (debug == true) { printf("Creating block with ID: %d\n", id); }
  268. uint8_t Hi[5] = {0x2,0x5,0x9,0xB,0xE};
  269. nextBlock = block(id,blck,Hi);
  270. } else {
  271. if (debug == true) { printf("Creating block with ID: %d\n", id); }
  272. uint8_t Hi[5] = {nextBlock[0],nextBlock[1],nextBlock[2],nextBlock[3],nextBlock[4]};
  273. nextBlock = block(id,blck,Hi);
  274. }
  275. }
  276. // Print results
  277. if (debug == true) { printf("Final Hash value \n"); }
  278. if (debug == true) { printf("A: %#x\n", nextBlock[0]); }
  279. if (debug == true) { printf("B: %#x\n", nextBlock[1]); }
  280. if (debug == true) { printf("C: %#x\n", nextBlock[2]); }
  281. if (debug == true) { printf("D: %#x\n", nextBlock[3]); }
  282. if (debug == true) { printf("E: %#x\n", nextBlock[4]); }
  283. // Free memory on the Heap
  284. free(msg_r);
  285. // Finish
  286. // if (debug == true) { clock_t end_h = clock(); }
  287. // if (debug == true) { double time_h = (double)(end_h-start_h)/CLOCKS_PER_SEC; }
  288. // if (debug == true) { printf("hash speed: %f \n", time_h); }
  289. return nextBlock;
  290. }
  291.  
  292. uint8_t *block (int blockID, uint8_t *xi, uint8_t *Hi) {
  293.  
  294. if (debug == true) { printf("process block %d\n", blockID); }
  295. if (debug == true) { printf("ABCDE = %#x %#x %#x %#x %#x \n", Hi[0], Hi[1], Hi[2], Hi[3], Hi[4] ); }
  296.  
  297. // left shift with carry for 4 bit
  298. // (foo << 1 | foo >> 3)
  299. // & 0xF to mask the leading bit
  300. for (int i=5; i<20;i++){
  301. uint8_t num = xi[i-1]^xi[i-4]^xi[i-5];
  302. num = (num << 1 | num >> 3) & 0xF;
  303. if (debug == true) { printf("%#x\n", num); }
  304. xi[i] = num;
  305. }
  306.  
  307. // Copy the ABCDE array for later use
  308. uint8_t H15[5] = {Hi[0],Hi[1],Hi[2],Hi[3],Hi[4]};
  309.  
  310. if (debug == true) { printf("begin round 1\n"); }
  311.  
  312. for (int i=0; i<10;i++){
  313. if (debug == true) { printf("step %d\n", i); }
  314. // components
  315. uint8_t A = Hi[0];
  316. A = (A << 1 | A >> 3) & 0xF;
  317. uint8_t F = (Hi[1]&Hi[2])|(~Hi[1]&Hi[3]) & 0xF;
  318. uint8_t Xi = xi[i];
  319. uint8_t E = Hi[4];
  320. // product in modulo arithmatic 2^4
  321. uint8_t t = (A + F + Xi + E)%0x10;
  322. // temp variables
  323. uint8_t tempA = Hi[0];
  324. uint8_t tempB = Hi[1];
  325. uint8_t tempC = Hi[2];
  326. uint8_t tempD = Hi[3];
  327. // remap
  328. // shift t i times
  329. for (int j = 1; j <= i; j++){
  330. t = (t << 1 | t >> 3) & 0xF;
  331. }
  332. // shift b 3 times
  333. for (int j = 1; j <= 3; j++){
  334. tempB = (tempB << 1 | tempB >> 3) & 0xF;
  335. }
  336. Hi[0] = t; if (debug == true) { printf("%#x\n", Hi[0]); }
  337. Hi[1] = tempA; if (debug == true) { printf("%#x\n", Hi[1]); }
  338. Hi[2] = tempB; if (debug == true) { printf("%#x\n", Hi[2]); }
  339. Hi[3] = tempC; if (debug == true) { printf("%#x\n", Hi[3]); }
  340. Hi[4] = tempD; if (debug == true) { printf("%#x\n", Hi[4]); }
  341. }
  342.  
  343. if (debug == true) { printf("begin round 2\n"); }
  344.  
  345. for (int i=10; i<20;i++){
  346. if (debug == true) { printf("step %d\n", i); }
  347. // components
  348. uint8_t A = Hi[0];
  349. // shift A i times
  350. for (int j = 1; j <= 3; j++){
  351. A = (A << 1 | A >> 3) & 0xF;
  352. }
  353. uint8_t G = (Hi[1]&Hi[3])|(Hi[2]&(~Hi[3])) & 0xF;
  354. uint8_t Xi = xi[i];
  355. uint8_t E = Hi[4];
  356. // product in modulo arithmatic 2^4
  357. uint8_t t = (A + G + Xi + E)%0x10;
  358. // temp variables
  359. uint8_t tempA = Hi[0];
  360. uint8_t tempB = Hi[1];
  361. uint8_t tempC = Hi[2];
  362. uint8_t tempD = Hi[3];
  363. // remap
  364. // shift t i times
  365. for (int j = 1; j <= i; j++){
  366. t = (t << 1 | t >> 3) & 0xF;
  367. }
  368. // shift b 3 times
  369. for (int j = 1; j <= 1; j++){
  370. tempB = (tempB << 1 | tempB >> 3) & 0xF;
  371. }
  372. Hi[0] = t; if (debug == true) { printf("%#x\n", Hi[0]); }
  373. Hi[1] = tempA; if (debug == true) { printf("%#x\n", Hi[1]); }
  374. Hi[2] = tempB; if (debug == true) { printf("%#x\n", Hi[2]); }
  375. Hi[3] = tempC; if (debug == true) { printf("%#x\n", Hi[3]); }
  376. Hi[4] = tempD; if (debug == true) { printf("%#x\n", Hi[4]); }
  377. }
  378.  
  379. if (debug == true) { printf("finalisation step\n"); }
  380.  
  381. uint8_t a = (Hi[0]+H15[0])%0x10;
  382. uint8_t b = (Hi[1]+H15[1])%0x10;
  383. uint8_t c = (Hi[2]+H15[2])%0x10;
  384. uint8_t d = (Hi[3]+H15[3])%0x10;
  385. uint8_t e = (Hi[4]+H15[4])%0x10;
  386.  
  387. int retElements = 5*sizeof(uint8_t);
  388. uint8_t *ret = (uint8_t *)malloc(retElements);
  389.  
  390. ret[0] = a; if (debug == true) { printf("A: %#x\n", ret[0]); }
  391. ret[1] = b; if (debug == true) { printf("B: %#x\n", ret[1]); }
  392. ret[2] = c; if (debug == true) { printf("C: %#x\n", ret[2]); }
  393. ret[3] = d; if (debug == true) { printf("D: %#x\n", ret[3]); }
  394. ret[4] = e; if (debug == true) { printf("E: %#x\n", ret[4]); }
  395.  
  396. //free(xi);
  397. //free(Hi);
  398.  
  399. return ret;
  400. }
  401.  
  402. int main(int argc,char **argv) {
  403. debug = false;
  404. hex = (uint8_t *)malloc(16 * sizeof(uint8_t));
  405. hex[0] = 0x0; hex[1] = 0x1; hex[2] = 0x2; hex[3] = 0x3; hex[4] = 0x4; hex[5] = 0x5;
  406. hex[6] = 0x6; hex[7] = 0x7; hex[8] = 0x8; hex[9] = 0x9; hex[10] = 0xA; hex[11] = 0xB;
  407. hex[12] = 0xC; hex[13] = 0xD; hex[14] = 0xE; hex[15] = 0xF;
  408.  
  409. //debug_messages();
  410. //exercise_messages();
  411. bruteforce_messages();
  412.  
  413. free(hex);
  414.  
  415. return 0;
  416. }
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!