tag:blogger.com,1999:blog-13881181204431708952024-03-14T06:14:35.225-07:00kutio's blogexploitation, reverse engineering, cryptography, lattices, liblll, knapsackkutiohttp://www.blogger.com/profile/17775395880749568836noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-1388118120443170895.post-7321808865912346372013-11-17T08:03:00.001-08:002013-11-17T08:36:27.364-08:00AES Sbox and Pari/GP<div dir="ltr" style="text-align: left;" trbidi="on">
<span style="font-family: Arial, Helvetica, sans-serif;">Hello folks !</span><br />
<div style="text-align: justify;">
<span style="font-family: Arial, Helvetica, sans-serif;">Lately I was interested in how to mathematically generate the AES substitution box. Actually, all the implementations of AES use a pre-filled table to compute the value of a substituted byte. The goal of this article is to understand how this table is computed.</span></div>
<div style="text-align: justify;">
<span style="font-family: Arial, Helvetica, sans-serif;">In a first part, we will describe the mathematical transformation and in the second part we will see how to do the mathematical transformation of the Sbox with Pari-GP. Because of my crappy level in mathematics, this article can be mathematically wrong or incorrect, so if you have advices, you are welcome :).</span></div>
<span style="font-family: Arial, Helvetica, sans-serif;"><br /></span>
<span style="font-family: Arial, Helvetica, sans-serif;">The goal of the article is to understand how to find this table :</span><br />
<span style="font-family: Arial, Helvetica, sans-serif;"><br /></span>
<br />
<pre style="background-color: #f9f9f9; border: 1px solid rgb(221, 221, 221); font-size: 13px; line-height: 1.3em; padding: 1em;"><span style="font-family: inherit;"> | 0 1 2 3 4 5 6 7 8 9 a b c d e f
---|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|
00 |63 7c 77 7b f2 6b 6f c5 30 01 67 2b fe d7 ab 76
10 |ca 82 c9 7d fa 59 47 f0 ad d4 a2 af 9c a4 72 c0
20 |b7 fd 93 26 36 3f f7 cc 34 a5 e5 f1 71 d8 31 15
30 |04 c7 23 c3 18 96 05 9a 07 12 80 e2 eb 27 b2 75
40 |09 83 2c 1a 1b 6e 5a a0 52 3b d6 b3 29 e3 2f 84
50 |53 d1 00 ed 20 fc b1 5b 6a cb be 39 4a 4c 58 cf
60 |d0 ef aa fb 43 4d 33 85 45 f9 02 7f 50 3c 9f a8
70 |51 a3 40 8f 92 9d 38 f5 bc b6 da 21 10 ff f3 d2
80 |cd 0c 13 ec 5f 97 44 17 c4 a7 7e 3d 64 5d 19 73
90 |60 81 4f dc 22 2a 90 88 46 ee b8 14 de 5e 0b db
a0 |e0 32 3a 0a 49 06 24 5c c2 d3 ac 62 91 95 e4 79
b0 |e7 c8 37 6d 8d d5 4e a9 6c 56 f4 ea 65 7a ae 08
c0 |ba 78 25 2e 1c a6 b4 c6 e8 dd 74 1f 4b bd 8b 8a
d0 |70 3e b5 66 48 03 f6 0e 61 35 57 b9 86 c1 1d 9e
e0 |e1 f8 98 11 69 d9 8e 94 9b 1e 87 e9 ce 55 28 df
f0 |8c a1 89 0d bf e6 42 68 41 99 2d 0f b0 54 bb 16 </span></pre>
<span style="font-family: Arial, Helvetica, sans-serif;"><br /></span>
<br />
<a name='more'></a><span style="font-family: Arial, Helvetica, sans-serif;"><br /></span>
<b><span style="font-family: Arial, Helvetica, sans-serif; font-size: x-large;">The mathematics behind the AES substitution</span></b><br />
<span style="font-family: Arial, Helvetica, sans-serif;"><br /></span>
<br />
<div style="text-align: justify;">
<span style="font-family: Arial, Helvetica, sans-serif;">In this article we want to find the substitute value for any byte ( noted here <b>b</b> ). The value is simply computed using an affine transformation :</span></div>
<span style="font-family: Arial, Helvetica, sans-serif;"><br /></span>
<b><span style="font-family: Arial, Helvetica, sans-serif;">SBOX(b) = A * inv_b + C</span></b><br />
<b><span style="font-family: Arial, Helvetica, sans-serif;"><br /></span></b>
<b><span style="font-family: Arial, Helvetica, sans-serif;">Remarks :</span></b><br />
<b><span style="font-family: Arial, Helvetica, sans-serif;"><br /></span></b>
<span style="font-family: Arial, Helvetica, sans-serif;"><b>A</b> is a rotational matrix based on the value <b>0x1F</b></span><br />
<span style="font-family: Arial, Helvetica, sans-serif;"><b><br /></b></span>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgAVGl3I89tezNtCVilWn9mTxbXUabNcLZlBXT4-OlSe3m6xckejD4wSd6tLc9de49r1waUD0cOv1TvzMSeJHDvw8aTRQ2q8au0kpH5zE1uejIVqNUeqPE6t0dKwg3YG9JStH9ea-anQDCb/s1600/A.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgAVGl3I89tezNtCVilWn9mTxbXUabNcLZlBXT4-OlSe3m6xckejD4wSd6tLc9de49r1waUD0cOv1TvzMSeJHDvw8aTRQ2q8au0kpH5zE1uejIVqNUeqPE6t0dKwg3YG9JStH9ea-anQDCb/s1600/A.png" /></a></div>
<span style="font-family: Arial, Helvetica, sans-serif;"><b><br /></b></span>
<span style="font-family: Arial, Helvetica, sans-serif;"><b>C </b>is the vector based on the value <b>0x63</b></span><br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgBMv_LRXUyZnPqrbreYIV98LnhxOwQjwf-lSNEaC332-MNWmsnCPjw5hMyZHli71oQnp0oFKvhZ_0yePtE8Bx_JB4Tpe_GzoLrjWpKvcr-4H-pN88915sUBorqzTXdWw4XI7ZAAb8kSWAH/s1600/C.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgBMv_LRXUyZnPqrbreYIV98LnhxOwQjwf-lSNEaC332-MNWmsnCPjw5hMyZHli71oQnp0oFKvhZ_0yePtE8Bx_JB4Tpe_GzoLrjWpKvcr-4H-pN88915sUBorqzTXdWw4XI7ZAAb8kSWAH/s1600/C.png" /></a></div>
<b><span style="font-family: Arial, Helvetica, sans-serif;"><br /></span></b>
<br />
<div style="text-align: justify;">
<span style="background-color: #fdfdfd; color: #111111; line-height: 19.59375px;"><span style="font-family: Arial, Helvetica, sans-serif;">The multiplication with <b>A </b>and the addition with <b>C</b> are performed in the field <b>GF(2) </b>(x mod 2). To popularize, it means that the coefficients of the matrix <b>A</b> and the vector <b>C</b> are modulo two and the <b>+ </b>operation is a <b>XOR</b>.</span></span></div>
<div style="text-align: justify;">
<span style="background-color: #fdfdfd; color: #111111; line-height: 19.59375px;"><span style="font-family: Arial, Helvetica, sans-serif;"><br /></span></span></div>
<div style="text-align: justify;">
<span style="font-family: Arial, Helvetica, sans-serif;"><span style="background-color: #fdfdfd; color: #111111; line-height: 19.59375px;">The affine transformation can be summarized </span><span style="color: #111111;"><span style="line-height: 19.59375px;">(over <b>GF(2)</b>)</span></span><span style="background-color: #fdfdfd; color: #111111; line-height: 19.59375px;">:</span></span></div>
<span style="background-color: #fdfdfd; color: #111111; line-height: 19.59375px;"><span style="font-family: Arial, Helvetica, sans-serif;"><br /></span></span>
<span style="font-family: Arial, Helvetica, sans-serif;"><b>SBOX(b(i)) = </b><span style="color: #111111; line-height: 19.59375px;"> <b>inv_b(i) XOR </b></span><span style="color: #111111; line-height: 19.59375px;"> <b>inv_b(i+4 mod 8) </b></span><span style="color: #111111; line-height: 19.59375px;"> <b>XOR </b></span><span style="color: #111111; line-height: 19.59375px;"> </span><b style="color: #111111; line-height: 19.59375px;">inv_b(i+5 mod 8) XOR </b><span style="color: #111111; line-height: 19.59375px;"> </span><b style="color: #111111; line-height: 19.59375px;">inv_b(i+6 mod 8) XOR </b><b style="color: #111111; line-height: 19.59375px;">inv_b(i+7 mod 8) XOR C(i), with i = 0..7</b></span><br />
<br />
<div style="text-align: left;">
<span style="font-family: Arial, Helvetica, sans-serif;"><span style="color: #111111;"><span style="line-height: 19.59375px;">Actually, the <b>delicate </b>point is to understand how <b>inv_b</b> is computed. The vector <b>inv_b </b>is the representation of the inverse of <b>b </b>in</span></span><span style="background-color: white; line-height: 19.1875px; text-align: left;"> <b>GF(2)[</b></span><i style="background-color: white; font-weight: bold; line-height: 19.1875px; text-align: left;">x</i><span style="background-color: white; font-weight: bold; line-height: 19.1875px; text-align: left;">]/(</span><i style="background-color: white; font-weight: bold; line-height: 19.1875px; text-align: left;">x</i><sup style="background-color: white; font-weight: bold; line-height: 1em; text-align: left;">8</sup><span style="background-color: white; font-weight: bold; line-height: 19.1875px; text-align: left;"> + </span><i style="background-color: white; font-weight: bold; line-height: 19.1875px; text-align: left;">x</i><sup style="background-color: white; font-weight: bold; line-height: 1em; text-align: left;">4</sup><span style="background-color: white; font-weight: bold; line-height: 19.1875px; text-align: left;"> + </span><i style="background-color: white; font-weight: bold; line-height: 19.1875px; text-align: left;">x</i><sup style="background-color: white; font-weight: bold; line-height: 1em; text-align: left;">3</sup><span style="background-color: white; font-weight: bold; line-height: 19.1875px; text-align: left;"> + </span><i style="background-color: white; font-weight: bold; line-height: 19.1875px; text-align: left;">x</i><span style="background-color: white; line-height: 19.1875px; text-align: left;"><b> + 1)</b>. That means, <b>b </b>or his <b>inverse</b> can be represented </span><span style="line-height: 19.1875px; text-align: left;">as a polynomial with coefficients in <b>GF(2)</b> modulo the polynomial </span><i style="background-color: white; font-weight: bold; line-height: 19.1875px;">x</i><sup style="background-color: white; font-weight: bold; line-height: 1em;">8</sup><span style="background-color: white; font-weight: bold; line-height: 19.1875px;"> + </span><i style="background-color: white; font-weight: bold; line-height: 19.1875px;">x</i><sup style="background-color: white; font-weight: bold; line-height: 1em;">4</sup><span style="background-color: white; font-weight: bold; line-height: 19.1875px;"> + </span><i style="background-color: white; font-weight: bold; line-height: 19.1875px;">x</i><sup style="background-color: white; font-weight: bold; line-height: 1em;">3</sup><span style="background-color: white; font-weight: bold; line-height: 19.1875px;"> + </span><i style="background-color: white; font-weight: bold; line-height: 19.1875px;">x</i><span style="background-color: white; line-height: 19.1875px;"><b> + 1</b>. In fact any byte can be written as a polynomial (for more information, see : <b>FIPS-197 - </b></span><span style="line-height: 19.1875px;"><b>3.2 Bytes</b>)</span></span></div>
<div style="text-align: left;">
<span style="background-color: white; font-family: Arial, Helvetica, sans-serif; font-size: 13px; line-height: 19.1875px;"><br /></span></div>
<div style="text-align: left;">
<b><span style="font-family: Arial, Helvetica, sans-serif;"><span style="background-color: white; line-height: 19.1875px;">0x63 = 0110 0011 = x^6 + </span><span style="background-color: white; line-height: 19.1875px;"> </span><span style="background-color: white; line-height: 19.1875px;">x^5 + </span><span style="background-color: white; line-height: 19.1875px;">x + 1</span></span></b></div>
<div style="text-align: left;">
<b><span style="font-family: Arial, Helvetica, sans-serif;"><span style="background-color: white; line-height: 19.1875px;">0x8E = 1000 1110 = x^7 + </span><span style="background-color: white; line-height: 19.1875px;"> </span><span style="background-color: white; line-height: 19.1875px;">x^3 + </span><span style="background-color: white; line-height: 19.1875px;">x^2 + x</span></span></b></div>
<div style="text-align: left;">
<span style="background-color: white; line-height: 19.1875px;"><b><span style="font-family: Arial, Helvetica, sans-serif;"><br /></span></b></span></div>
<div style="text-align: left;">
<span style="font-family: Arial, Helvetica, sans-serif;"><span style="line-height: 19.1875px;">To resume how the inverse of <b>b</b> is computed :</span></span></div>
<div style="text-align: left;">
<span style="font-family: Arial, Helvetica, sans-serif;"><span style="line-height: 19.1875px;"><br /></span></span></div>
<div style="text-align: left;">
<span style="font-family: Arial, Helvetica, sans-serif;"><span style="line-height: 19.1875px;"><b>inv_b = inv(b) = Mod(b*Mod(1, 2), (x^8 + x^4 + x^3 + x + 1)</b></span><b style="line-height: 19.1875px;">*Mod(1, 2)</b><b style="line-height: 19.1875px;">)^-1</b></span></div>
<div style="text-align: left;">
<span style="font-family: Arial, Helvetica, sans-serif;"><b style="line-height: 19.1875px;"><br /></b></span></div>
<div style="text-align: left;">
<span style="font-family: Arial, Helvetica, sans-serif; font-size: x-large;"><b>Find the substitute value with PARI/GP</b></span></div>
<div style="text-align: left;">
<span style="font-family: Arial, Helvetica, sans-serif; text-align: justify;"><br /></span></div>
<div style="text-align: left;">
<span style="font-family: Arial, Helvetica, sans-serif; text-align: justify;">In this part, we will see how to find the <b>AES </b>substitute value for any byte with <b>PARI/GP</b>. To do that we will try to find the <b>SBOX </b>value of <b>0x23 </b>(which is <b>0x26</b>).</span></div>
<div style="text-align: left;">
<span style="font-family: Arial, Helvetica, sans-serif; text-align: justify;"><br /></span></div>
<div style="text-align: justify;">
<span style="font-family: Arial, Helvetica, sans-serif;">The first step is to represent <b>0x23 </b>as a polynomial and find his inverse in </span><span style="background-color: white; font-family: Arial, Helvetica, sans-serif; line-height: 19.1875px; text-align: left;"> <b>GF(2)[</b></span><i style="background-color: white; font-family: Arial, Helvetica, sans-serif; font-weight: bold; line-height: 19.1875px; text-align: left;">x</i><span style="background-color: white; font-family: Arial, Helvetica, sans-serif; font-weight: bold; line-height: 19.1875px; text-align: left;">]/(</span><i style="background-color: white; font-family: Arial, Helvetica, sans-serif; font-weight: bold; line-height: 19.1875px; text-align: left;">x</i><sup style="background-color: white; font-family: Arial, Helvetica, sans-serif; font-weight: bold; line-height: 1em; text-align: left;">8</sup><span style="background-color: white; font-family: Arial, Helvetica, sans-serif; font-weight: bold; line-height: 19.1875px; text-align: left;"> + </span><i style="background-color: white; font-family: Arial, Helvetica, sans-serif; font-weight: bold; line-height: 19.1875px; text-align: left;">x</i><sup style="background-color: white; font-family: Arial, Helvetica, sans-serif; font-weight: bold; line-height: 1em; text-align: left;">4</sup><span style="background-color: white; font-family: Arial, Helvetica, sans-serif; font-weight: bold; line-height: 19.1875px; text-align: left;"> + </span><i style="background-color: white; font-family: Arial, Helvetica, sans-serif; font-weight: bold; line-height: 19.1875px; text-align: left;">x</i><sup style="background-color: white; font-family: Arial, Helvetica, sans-serif; font-weight: bold; line-height: 1em; text-align: left;">3</sup><span style="background-color: white; font-family: Arial, Helvetica, sans-serif; font-weight: bold; line-height: 19.1875px; text-align: left;"> + </span><i style="background-color: white; font-family: Arial, Helvetica, sans-serif; font-weight: bold; line-height: 19.1875px; text-align: left;">x</i><span style="background-color: white; font-family: Arial, Helvetica, sans-serif; line-height: 19.1875px; text-align: left;"><b> + 1)</b> :</span></div>
<div style="text-align: justify;">
<span style="background-color: white; font-family: Arial, Helvetica, sans-serif; line-height: 19.1875px; text-align: left;"><b><br /></b></span></div>
<div style="text-align: justify;">
<span style="background-color: white; font-family: Arial, Helvetica, sans-serif; line-height: 19.1875px; text-align: left;"><b>0x23 = 0010 0011 = x^5 + x + 1</b></span></div>
<div style="text-align: justify;">
<span style="background-color: white; font-family: Arial, Helvetica, sans-serif; line-height: 19.1875px; text-align: left;"><b><br /></b></span></div>
<div style="text-align: justify;">
<span style="background-color: white; line-height: 19.1875px; text-align: left;"><span style="font-family: Arial, Helvetica, sans-serif;"><b> gp > inv_b = Mod(b*Mod(1, 2), (x^8+x^4+x^3+x+1)*Mod(1, 2))^-1</b></span></span></div>
<div style="text-align: justify;">
<span style="background-color: white; line-height: 19.1875px; text-align: left;"><span style="font-family: Arial, Helvetica, sans-serif;"><b> gp > lift(lift(inv_b))</b></span></span></div>
<div style="text-align: justify;">
<span style="background-color: white; line-height: 19.1875px; text-align: left;"><span style="font-family: Arial, Helvetica, sans-serif;"><b>%35 = </b></span></span><span style="line-height: 19.1875px; text-align: left;"><span style="font-family: Arial, Helvetica, sans-serif;"><b>x^7 + x^6 + x^5 + x^4 + 1</b></span></span></div>
<div style="text-align: justify;">
<span style="background-color: white; line-height: 19.1875px; text-align: left;"><span style="font-family: Arial, Helvetica, sans-serif;"><b><br /></b></span></span></div>
<div style="text-align: left;">
<span style="font-family: Arial, Helvetica, sans-serif;"><span style="line-height: 19.1875px;"><b>x^7 + x^6 + x^5 + x^4 + 1 = 1111 0001 = 0xF1</b></span></span></div>
<div style="text-align: justify;">
<span style="background-color: white; line-height: 19.1875px; text-align: left;"><span style="font-family: Arial, Helvetica, sans-serif;"><b><br /></b></span></span></div>
<div style="text-align: left;">
<span style="font-family: Arial, Helvetica, sans-serif;"><span style="line-height: 19.1875px;">The inverse of <b>0x23 </b>in </span></span><span style="background-color: white; font-family: Arial, Helvetica, sans-serif; line-height: 19.1875px;"><b>GF(2)[</b></span><i style="background-color: white; font-family: Arial, Helvetica, sans-serif; font-weight: bold; line-height: 19.1875px;">x</i><span style="background-color: white; font-family: Arial, Helvetica, sans-serif; font-weight: bold; line-height: 19.1875px;">]/(</span><i style="background-color: white; font-family: Arial, Helvetica, sans-serif; font-weight: bold; line-height: 19.1875px;">x</i><sup style="background-color: white; font-family: Arial, Helvetica, sans-serif; font-weight: bold; line-height: 1em;">8</sup><span style="background-color: white; font-family: Arial, Helvetica, sans-serif; font-weight: bold; line-height: 19.1875px;"> + </span><i style="background-color: white; font-family: Arial, Helvetica, sans-serif; font-weight: bold; line-height: 19.1875px;">x</i><sup style="background-color: white; font-family: Arial, Helvetica, sans-serif; font-weight: bold; line-height: 1em;">4</sup><span style="background-color: white; font-family: Arial, Helvetica, sans-serif; font-weight: bold; line-height: 19.1875px;"> + </span><i style="background-color: white; font-family: Arial, Helvetica, sans-serif; font-weight: bold; line-height: 19.1875px;">x</i><sup style="background-color: white; font-family: Arial, Helvetica, sans-serif; font-weight: bold; line-height: 1em;">3</sup><span style="background-color: white; font-family: Arial, Helvetica, sans-serif; font-weight: bold; line-height: 19.1875px;"> + </span><i style="background-color: white; font-family: Arial, Helvetica, sans-serif; font-weight: bold; line-height: 19.1875px;">x</i><span style="background-color: white; font-family: Arial, Helvetica, sans-serif; line-height: 19.1875px;"><b> + 1) </b>is <b>0xF1</b>.</span></div>
<div style="text-align: left;">
<span style="background-color: white; font-family: Arial, Helvetica, sans-serif; line-height: 19.1875px;"><br /></span></div>
<div style="text-align: left;">
<span style="font-family: Arial, Helvetica, sans-serif;"><span style="line-height: 19.1875px;">Now we have <b>inv_b</b>, we can compute the affine transformation in <b>GF(2) :</b></span></span></div>
<div style="text-align: left;">
<span style="font-family: Arial, Helvetica, sans-serif;"><span style="line-height: 19.1875px;"><b><br /></b></span></span></div>
<div style="text-align: left;">
<b><span style="font-family: Arial, Helvetica, sans-serif;">SBOX(b) = A * inv_b + C</span></b></div>
<div style="text-align: left;">
<b><span style="font-family: Arial, Helvetica, sans-serif;"><br /></span></b></div>
<div style="text-align: left;">
<span style="font-family: Arial, Helvetica, sans-serif;">We initialize the matrix <b>A, </b>the vector <b>C</b> and <b>inv_b </b> ( be careful at the endianess representation for the vector)</span></div>
<div style="text-align: left;">
<span style="font-family: Arial, Helvetica, sans-serif;"><b><br /></b></span></div>
<div style="text-align: left;">
<b style="background-color: white; font-family: Arial, Helvetica, sans-serif; line-height: 19.1875px;"> gp ></b><b><span style="font-family: Arial, Helvetica, sans-serif;"> </span></b><span style="font-family: Arial, Helvetica, sans-serif;"><b>A = [1, 0, 0, 0, 1, 1, 1, 1; 1, 1, 0, 0, 0, 1, 1, 1 ; 1, 1, 1, 0, 0, 0, 1, 1 ; 1, 1, 1, 1, 0, 0, 0, 1; 1, 1, 1, 1, 1, 0, 0, 0 ; 0, 1, 1, 1, 1, 1, 0, 0 ; 0, 0, 1, 1, 1, 1, 1, 0 ; 0, 0, 0, 1, 1, 1, 1, 1]*Mod(1, 2)</b></span></div>
<div style="text-align: left;">
<b style="background-color: white; font-family: Arial, Helvetica, sans-serif; line-height: 19.1875px;"> gp > C </b><span style="font-family: Arial, Helvetica, sans-serif;"><span style="line-height: 19.1875px;"><b> = [1, 1, 0, 0, 0, 1, 1, 0]~*Mod(1, 2)</b></span></span></div>
<div style="text-align: left;">
<b style="background-color: white; font-family: Arial, Helvetica, sans-serif; line-height: 19.1875px;"> gp > inv_b = [</b><b style="font-family: Arial, Helvetica, sans-serif; line-height: 19.1875px;">1, 0, 0, 0, 1, 1, 1, 1]~</b><b style="font-family: Arial, Helvetica, sans-serif; line-height: 19.1875px;">*Mod(1, 2)</b></div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
<span style="font-family: Arial, Helvetica, sans-serif; line-height: 19.1875px;">And we apply the transformation :</span></div>
<div style="text-align: left;">
<span style="font-family: Arial, Helvetica, sans-serif; line-height: 19.1875px;"><br /></span></div>
<div style="text-align: left;">
<b style="font-family: Arial, Helvetica, sans-serif; line-height: 19.1875px;">gp > sbox_b = (A * inv_b) + C</b></div>
<div style="text-align: left;">
<b style="font-family: Arial, Helvetica, sans-serif; line-height: 19.1875px;">gp ></b><b style="background-color: white; font-family: Arial, Helvetica, sans-serif; line-height: 19.1875px;"> lift(lift(</b><b style="font-family: Arial, Helvetica, sans-serif; line-height: 19.1875px;">sbox_b</b><b style="background-color: white; font-family: Arial, Helvetica, sans-serif; line-height: 19.1875px;">))</b></div>
<div style="text-align: left;">
<span style="font-family: Arial, Helvetica, sans-serif;"><span style="line-height: 19.1875px;"><b>%76 = [0, 1, 1, 0, 0, 1, 0, 0]~</b></span></span></div>
<div style="text-align: left;">
<span style="font-family: Arial, Helvetica, sans-serif;"><span style="line-height: 19.1875px;"><b><br /></b></span></span></div>
<div style="text-align: left;">
<span style="font-family: Arial, Helvetica, sans-serif;"><span style="line-height: 19.1875px;"><b>0010 0110 = 0x26</b></span></span></div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
<span style="font-family: Arial, Helvetica, sans-serif;">If we read our <b>SBOX</b> table, the value <b>0x23</b> is well transformed in <b>0x26 </b>!</span></div>
<div style="text-align: left;">
<span style="font-family: Arial, Helvetica, sans-serif;"><br /></span></div>
<div style="text-align: left;">
<span style="font-family: Arial, Helvetica, sans-serif;"><br /></span></div>
<span style="font-family: Arial, Helvetica, sans-serif; font-size: x-large;"><b>Conclusion</b></span><br />
<div>
</div>
<div>
<span style="font-family: Arial, Helvetica, sans-serif;">To conclude, </span><span style="font-family: Arial, Helvetica, sans-serif;">the pre-computed <b>SBOX </b>table does not come out of a hat, and there is a real mathematical approach to compute the values.</span></div>
<div>
<span style="font-family: Arial, Helvetica, sans-serif;"><br /></span></div>
<div>
<span style="font-family: Arial, Helvetica, sans-serif;"><br /></span></div>
<h2 style="text-align: left;">
<b style="font-family: Arial, Helvetica, sans-serif;"><span style="font-size: x-large;">Documentation :</span></b></h2>
<b><span style="font-family: Arial, Helvetica, sans-serif;">ADVANCED ENCRYPTION STANDARD (AES) :</span></b><br />
<span style="font-family: Arial, Helvetica, sans-serif;"><a href="http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf">http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf</a></span><br />
<br />
<b style="border: 0px; cursor: pointer; font-family: Arial, Helvetica, sans-serif; line-height: 1.3; margin: 0px 0px 1.2em; padding: 0px; text-decoration: none; vertical-align: baseline;"><span style="line-height: 1.3; margin-bottom: 1.2em;">R</span>ijndael S-box</b><br />
<a href="http://en.wikipedia.org/wiki/Rijndael_S-box">http://en.wikipedia.org/wiki/Rijndael_S-box</a><br />
<br />
<span style="border: 0px; cursor: pointer; font-family: Arial, Helvetica, sans-serif; font-size: small; line-height: 1.3; margin: 0px 0px 1.2em; padding: 0px; text-decoration: none; vertical-align: baseline;"><b>How are the AES S-Boxes calculated?</b></span><br />
<div style="text-align: left;">
<a href="http://crypto.stackexchange.com/questions/10996/how-are-the-aes-s-boxes-calculated"><span style="font-family: Arial, Helvetica, sans-serif;">http://crypto.stackexchange.com/questions/10996/how-are-the-aes-s-boxes-calculated</span></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div style="text-align: left;">
<span style="font-family: Arial, Helvetica, sans-serif; text-align: justify;"><br /></span></div>
</div>
kutiohttp://www.blogger.com/profile/17775395880749568836noreply@blogger.com0tag:blogger.com,1999:blog-1388118120443170895.post-33963774129510546912013-05-30T10:45:00.000-07:002017-02-04T00:27:35.338-08:00NoSuchCon 2013 challenge - Write up and Methodology<div dir="ltr" style="text-align: left;" trbidi="on">
I had to do a write-up for the NoSuchCon 2013 challenge to get my "usb missile launcher". I wanted to share this write-up to give some approaches to do the challenge. I’m really interested to have feedback, comments or ideas to improve the process.<br />
In the first section of this paper, we will see the methodology to break the challenge, even the bad ideas. Then we will see how to automate the deobfuscation. In the third section, we will see how to attack the algorithm and we will end up with a small conclusion.<br />
<br />
<div style="text-align: left;">
The link :<a href="https://github.com/kutio/nosuchcon2013-challenge/raw/master/doc/NoSuchCon2013-re-chall-writeup-v1.0.pdf" target="_blank"> https://github.com/kutio/nosuchcon2013-challenge/raw/master/doc/NoSuchCon2013-re-chall-writeup-v1.0.pdf</a></div>
<div style="text-align: left;">
The sources :<a href="https://github.com/kutio/nosuchcon2013-challenge" target="_blank"> https://github.com/kutio/nosuchcon2013-challenge</a>
</div>
<br />
<br />
<b>Greetz</b>: <a href="https://twitter.com/0vercl0k">@0vercl0k</a> who lost some neurones with me<br />
<a href="https://twitter.com/elvanderb">@elvanderb</a> with his crazy challenge<br />
<a href="https://twitter.com/skier_t">@skier</a> who gave me some clever ideas<br />
<div style="text-align: left;">
<a href="https://twitter.com/Taron__">@Taron__ </a> who reviewed the write-up</div>
</div>
kutiohttp://www.blogger.com/profile/17775395880749568836noreply@blogger.com0tag:blogger.com,1999:blog-1388118120443170895.post-86983381885113894282012-01-21T01:16:00.000-08:002013-06-08T02:36:11.184-07:00Breaking MD5 hashs<div dir="ltr" style="text-align: left;" trbidi="on">
Hello world!<br />
<br />
Here is an easy to understand article about breaking md5 hashs. Breaking md5 hashs is a subject really discussed on the Internet. If you are new in the hacking community, the first thing that you learn to do is to break md5 hashs. Actually a lot of developers use the md5 hash function to hash passwords before to store it in a database. So if a hacker is able to compromise a website or a system and he is able to retrieve the hashs, he has to break md5 hashs to recover plaintexts.<br />
To break a md5 hash there are a lot of technics, for example :<br />
<ul>
<li>Dictionary attack</li>
<li>Rainbow table attack</li>
<li>Brute force attack</li>
</ul>
<span class="" id="result_box" lang="en"><span class="hps">For courses</span> <span class="hps">I had a</span> <span class="hps">challenge</span> <span class="hps">where I</span> <span class="hps">had to break</span> 5 <span class="hps">md5</span> <span class="hps">hashs. So I wanted to write up how I proceeded to break this hashs. </span><span class="hps"></span></span> In our case, we know that the hashs are randomly generated so it will be difficult to retrieve the plaintext with a dictionary attack. Dictionary attacks are used<br />
when we know that people use common word of the dictionary for their password. We also know that the length of the passwords is between 6 and 10 characters. On the one hand we will see what material I used to break this challenge, on the other hand we will see how I proceeded to recover the plaintexts and then again we will see the good practices to have for a secure password.<br />
<br />
<a name='more'></a><br />
<b><span style="font-size: x-large;">Material for the challenge</span></b><br />
<br />
<span style="font-size: small;">To brute force this challenge, a simple personal computer was used. Here is the configuration of the computer :</span><br />
<ul>
<li>Intel Core i5 CPU 760 2.80Ghz 8 threads, 4 CPUs</li>
<li>ATI Radeon HD 6870</li>
<li>8.00Go of RAM</li>
</ul>
So it's not an amazing configuration, it's a personal computer. You can buy this configuration for 600 euros. To solve this challenge I chose to use my CPU<br />
and also my GPU because we know that the GPU is more efficient for brute force. With my configuration I noticed that with just my CPU I was able to test 1 000 000 hashs per second and with my GPU I was able to test 5 000 000 000 md5 hashs per second which is not negligible. We know that passwords are between<br />
6 and 10 characters length. Here is a comparison of performance to compute all passwords of 6 - 7 - 8 - 9 - 10 characters length with a charset of 81 characters using this computer.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhORRnL7VFl7BgE1IDLyGeG7XqXfjR-mKiueXUQYOUcMygblWb76LuZ_l46mQSlOscxJNj8rjWRNz1CgFyVxnRULdVawH4wiSNk6lfuMOSjgU92k8NGM8RCxgW0XD-Tx6ff_SyKu_w6oEQG/s1600/time_compute.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="172" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhORRnL7VFl7BgE1IDLyGeG7XqXfjR-mKiueXUQYOUcMygblWb76LuZ_l46mQSlOscxJNj8rjWRNz1CgFyVxnRULdVawH4wiSNk6lfuMOSjgU92k8NGM8RCxgW0XD-Tx6ff_SyKu_w6oEQG/s320/time_compute.png" width="320" /></a></div>
<br />
So as we can see with a naive brute force and this computer, it's annoying to brute force a password superior or equal of 8 characters length.<br />
And it's also impossible to brute force a password of 10 characters length.<br />
<br />
<br />
<b><span style="font-size: x-large;">Break MD5 hashs</span></b><br />
<br />
It exists a lot of password breaker programs ( or in a more ethical way "password recovery" programs), for example John the ripper, Durandal, cuda-md5-breaker,<br />
hashcat and so on... For my part I decided to use oclHashcat-plus because this one supports OpenCL (for my ATI Radeon GPU card), it's available on Windows and Linux, and I chose this program especially because it's easy to create his own heuristic to speed up the computation ( masking attack ). oclHashcat has also<br />
a really good <a href="http://hashcat.net/wiki/start">wiki</a> with a lot of documentation.<br />
When you want to break a md5 hash, the first thing to do is to check that this one doesn't exist in the database of an online md5 breaker (for example : <a href="http://www.md5decrypter.co.uk/">http://www.md5decrypter.co.uk</a>). In our case, thanks to this online md5 breaker I was able to recover the first hash :<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiMeEj7SibsZkO7AVpf7kUCSh5BbEp-wOr_J32HhCrxRGEF04zNIJDCeXxX12d0zF6ueK6V_9oA8fO0J4sSHFTeuBd5B6V6lUPAZStN7SBoexE4Qy4q2GPAwuGqbFxpw2ihnedQfv-HrLs2/s1600/first_hash.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="32" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiMeEj7SibsZkO7AVpf7kUCSh5BbEp-wOr_J32HhCrxRGEF04zNIJDCeXxX12d0zF6ueK6V_9oA8fO0J4sSHFTeuBd5B6V6lUPAZStN7SBoexE4Qy4q2GPAwuGqbFxpw2ihnedQfv-HrLs2/s400/first_hash.png" width="400" /></a></div>
With a brute force on the digit charset, it would have taken less than 1 second with our machine. So this password is really weak, the entropy of the password is :<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjG6AQrzWFfOj5uYr6dqO_2-K0Id63cLE8hyphenhyphennAcqAC_fCMM5j49js3lKB1Ux_DekYawT9GbvRODHw1kZDVShwiCCw3YvK8UailGknGr9YdTjqTGtWjtmok87naxo1cFXWylTcHzuz7ztP30/s1600/entropy_first_hash.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjG6AQrzWFfOj5uYr6dqO_2-K0Id63cLE8hyphenhyphennAcqAC_fCMM5j49js3lKB1Ux_DekYawT9GbvRODHw1kZDVShwiCCw3YvK8UailGknGr9YdTjqTGtWjtmok87naxo1cFXWylTcHzuz7ztP30/s1600/entropy_first_hash.png" /></a></div>
With oclHashcat-plus we can create our own heuristic easily. What I call heuristic is this :<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg-qBNUURWl-PHcKSN54MPv0qgBgBCj1PHgUeWQpISsIHBGWo3BkDIXuw5kg0JzYYae-5sZh8xsZsc8a7shwlclvtSv_RLwv5rE0mGsaJm-86T6Jh9g7IQGqxN8ozmtTVrZ6_IIq9_zUyLI/s1600/masking_attack.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="88" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg-qBNUURWl-PHcKSN54MPv0qgBgBCj1PHgUeWQpISsIHBGWo3BkDIXuw5kg0JzYYae-5sZh8xsZsc8a7shwlclvtSv_RLwv5rE0mGsaJm-86T6Jh9g7IQGqxN8ozmtTVrZ6_IIq9_zUyLI/s640/masking_attack.png" width="640" /></a></div>
And you can use it like this :<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgWkAQ3Qdu8LFUCO7kldRtQ5-4nIk0ZY903f4eMQ73M9dQdxbE0kt2lrcAkxEES6SnWgdOTatSkXLByntTJBPr6Scpe6bCa58r8twkQXPs_4cWeHjzKEkWEFgfq7j6KvyjKFLqn8E9HK8Cr/s1600/launch_masking_attack.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="32" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgWkAQ3Qdu8LFUCO7kldRtQ5-4nIk0ZY903f4eMQ73M9dQdxbE0kt2lrcAkxEES6SnWgdOTatSkXLByntTJBPr6Scpe6bCa58r8twkQXPs_4cWeHjzKEkWEFgfq7j6KvyjKFLqn8E9HK8Cr/s400/launch_masking_attack.png" width="400" /></a></div>
It's also possible to specify his own charset for each position of the password, which is really convenient to speed up the brute force. According to the document <a href="http://www.imperva.com/docs/WP_Consumer_Password_Worst_Practices.pdf">Consumer Password Wost Practices</a> of Imperva, the distribution of the password length is this one :<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiRWhWeiXbkkUTbYZF8McoTQK8nIVTGC8FghxPsr-qR2ldOMCP3w1h6LTRwASLYn9yVfzsKH8iPPDICTOEUTIHJYVzrQzBQK7kYV4CbEQtotEz3G2-8wjzWbxJJdsNT_b4RRrMANw3sFQ8B/s1600/password_length_distribution.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="296" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiRWhWeiXbkkUTbYZF8McoTQK8nIVTGC8FghxPsr-qR2ldOMCP3w1h6LTRwASLYn9yVfzsKH8iPPDICTOEUTIHJYVzrQzBQK7kYV4CbEQtotEz3G2-8wjzWbxJJdsNT_b4RRrMANw3sFQ8B/s320/password_length_distribution.png" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgDpvFhLYh3Zh6AjX5-FOtItY5TUurIHG0fEwOXt8S733UKxmTNVxT0XyQ98QMpYcMmvXRmPm0V58v2qGLv_iq4-b1S6Oht2ro-Rtpdx1nZYch_hfRROJJnPBcxT7JwUKVNG27CFncvInHy/s1600/password_set_character.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><br />
</a></div>
We also know that the repartition of characters is this one :<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgDpvFhLYh3Zh6AjX5-FOtItY5TUurIHG0fEwOXt8S733UKxmTNVxT0XyQ98QMpYcMmvXRmPm0V58v2qGLv_iq4-b1S6Oht2ro-Rtpdx1nZYch_hfRROJJnPBcxT7JwUKVNG27CFncvInHy/s1600/password_set_character.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="220" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgDpvFhLYh3Zh6AjX5-FOtItY5TUurIHG0fEwOXt8S733UKxmTNVxT0XyQ98QMpYcMmvXRmPm0V58v2qGLv_iq4-b1S6Oht2ro-Rtpdx1nZYch_hfRROJJnPBcxT7JwUKVNG27CFncvInHy/s400/password_set_character.png" width="400" /></a></div>
According to the document <a href="http://www.imperva.com/download.asp?id=293">Hacker Intelligence Initiative, Monthly Trend Report 7</a>, there are typical schemes:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiwwkWz9FRsWGyqO_GrheXK0lmk5fGYCGz4scKCv_IX6fRmu0gRXQ6Epci9G6ZrRcfAWrrhMKx1Oyr1kF4Egk5oghgGYZN-lQHVYE-jfneeo7HRcCLY1DUvuR2H6TA1sVUS_4DTEA8bUiiJ/s1600/password_scheme.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiwwkWz9FRsWGyqO_GrheXK0lmk5fGYCGz4scKCv_IX6fRmu0gRXQ6Epci9G6ZrRcfAWrrhMKx1Oyr1kF4Egk5oghgGYZN-lQHVYE-jfneeo7HRcCLY1DUvuR2H6TA1sVUS_4DTEA8bUiiJ/s320/password_scheme.png" width="294" /></a></div>
<br />
It's easy to deduce typical schemes for common passwords and to build good heuristics.<br />
Example of an advanced masking attack using a specified charset :<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjgRWfujdG9s0wTQLVLI_uczYf3ocSo4UHNpyyAuogg894MnUH5bohXNc_lDQrBsEwG4a7G9b22L4JrxEs2uzsqmqqrHUB522MCIiS4idxONb-rr85B4r5np_hs7yY_7g-ZdpTK5kIT7Xiy/s1600/advanced_masking.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="57" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjgRWfujdG9s0wTQLVLI_uczYf3ocSo4UHNpyyAuogg894MnUH5bohXNc_lDQrBsEwG4a7G9b22L4JrxEs2uzsqmqqrHUB522MCIiS4idxONb-rr85B4r5np_hs7yY_7g-ZdpTK5kIT7Xiy/s640/advanced_masking.png" width="640" /></a></div>
The entropy of this masking attack is :<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgwuiSvGyEI0FSDIHwJfYfKw3WxmYrvXZtFiVE4VAF4LGyApCfBeNsNmNyltLXkvUoDPkJ2Dj8lsK8Oewx4ujVxkhPdmYMGIH51xIJtQWs2CV5A8EZcwrHphUaBUFqCOLE1AZL0jAuDXQWC/s1600/entropy_advanced_masking_attack.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgwuiSvGyEI0FSDIHwJfYfKw3WxmYrvXZtFiVE4VAF4LGyApCfBeNsNmNyltLXkvUoDPkJ2Dj8lsK8Oewx4ujVxkhPdmYMGIH51xIJtQWs2CV5A8EZcwrHphUaBUFqCOLE1AZL0jAuDXQWC/s1600/entropy_advanced_masking_attack.png" /></a></div>
It's possible to do this masking attack in 5 minutes : <br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgtFzYc0QDv26O3T8GaABBDBvlaoA5hdggjiqnkP-pwIhH_pvjiGPpNdZZuKKqLPzIuUcVLkxJ8tzaxCgYyoGMbBSQIjDaftzIc1M4dqDPn8d4MUYzrBhfoWIN0cpQpraChp7pumt_R6vEe/s1600/period_time_advanced_masking_attack.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="36" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgtFzYc0QDv26O3T8GaABBDBvlaoA5hdggjiqnkP-pwIhH_pvjiGPpNdZZuKKqLPzIuUcVLkxJ8tzaxCgYyoGMbBSQIjDaftzIc1M4dqDPn8d4MUYzrBhfoWIN0cpQpraChp7pumt_R6vEe/s400/period_time_advanced_masking_attack.png" width="400" /></a></div>
<br />
We can compare it with a naive brute force attack, the entropy is :<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhmzZWmwFz5GwT9Kxz3zgl_uOjqUN-jKN88dRXBQosc6hg2mJm4Y7hebcVDRyE-z1reRW63JfSwVA9lgGJN43k1n091htI-fhTX_F4MRDwhN5x-IiHSWNiOXeae6I-U9KsnmjvWV8a76N2c/s1600/naive_bf_entropy.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhmzZWmwFz5GwT9Kxz3zgl_uOjqUN-jKN88dRXBQosc6hg2mJm4Y7hebcVDRyE-z1reRW63JfSwVA9lgGJN43k1n091htI-fhTX_F4MRDwhN5x-IiHSWNiOXeae6I-U9KsnmjvWV8a76N2c/s1600/naive_bf_entropy.png" /></a></div>
The computation time to do the attack is 4 days :<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgkaH-SY-2AUt5JRS9VFw5zvUlZ37ROpBIoXZmz_A9WIP6sQloQqJPvXEzPZDDjCN9fFddfzbZdSXl_2gwI4tCpRKXmE1GzxEL8HBqjbfYxNb0brTmk66sVp8MawvXZcWThlFUPQfvUUXqC/s1600/naive_bf_computation_time.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgkaH-SY-2AUt5JRS9VFw5zvUlZ37ROpBIoXZmz_A9WIP6sQloQqJPvXEzPZDDjCN9fFddfzbZdSXl_2gwI4tCpRKXmE1GzxEL8HBqjbfYxNb0brTmk66sVp8MawvXZcWThlFUPQfvUUXqC/s1600/naive_bf_computation_time.png" /></a></div>
The time saved is not negligible and that's why when there is a low entropy on passwords, heuristic attacks are really powerfull.<br />
Knowing these statistics, I was able to recover all the passwords really fast. Here is the table summarizing my masking attacks :<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEigDRdBcOCr5vpYHFWGDq_i_qPnNrurnp3I_r5imBr5lo1rYliLE9RaCUbb8vrqqiHSpTsuvi01bligloUprkwvy-WLZi3Uoctq-dQtWUzhZEYorC89LCsCNJBlM0kcXaKnwc-WWnW6fh3Z/s1600/table_final_hash.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="95" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEigDRdBcOCr5vpYHFWGDq_i_qPnNrurnp3I_r5imBr5lo1rYliLE9RaCUbb8vrqqiHSpTsuvi01bligloUprkwvy-WLZi3Uoctq-dQtWUzhZEYorC89LCsCNJBlM0kcXaKnwc-WWnW6fh3Z/s640/table_final_hash.png" width="640" /></a></div>
Note : the charset used for "?1" is the same charset of the above masking attack example.<br />
So with heuristic attacks we were able to retrieve quickly all the plaintexts. <br />
<br />
<br />
<b><span style="font-size: x-large;">Good practices</span></b><br />
<br />
A good password is a password with a good margin of security. What I mean by a good margin of security is even with a super computer ( a super computer<br />
can do ~ 10^16 tests per second ), you need all your life to brute force the password. So to set up a good password we have to fix the minimal<br />
length :<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiIntidsyzrHiPxiDMDPnl8__NZdySC7-WVnYPpxHYI09ZTodTb32RNT8aew_H7L-u9smTUJMdqqib84tjWlrjKLrvfL7pCbAPtyIQpDJqcfallDfejqomap_LuupeGvTcW7OxEQqsv2bE5/s1600/password_size.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="136" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiIntidsyzrHiPxiDMDPnl8__NZdySC7-WVnYPpxHYI09ZTodTb32RNT8aew_H7L-u9smTUJMdqqib84tjWlrjKLrvfL7pCbAPtyIQpDJqcfallDfejqomap_LuupeGvTcW7OxEQqsv2bE5/s400/password_size.png" width="400" /></a></div>
So the minimal length for your password should be 13 characters. The charset is the charset of 81 characters defined previously. But of course you can use<br />
a more complicated charset to increase the security margin. But this is not sufficient, the scheme of you password should be unpredictable, so with<br />
a maximal entropy. A way to generate your password is to take randomly 13 chars in the given charset. It's important to be sure of the security of your<br />
random function.<br />
<br />
Example of code to generate passwords :<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjfiYzaaYINXp-aDaSysFP3Z3ayNTK74YHnIiA6bz_6TUdKTId58wEEFtn5eXS44wIwnNAK6ycAzeLRd3g8k18glLYHVHxJrIRr5ZIwsUHDr9MBV7ZE0_VGG-m1sMyJ2H3kvKkqn4FmAO4E/s1600/gen_pass_python.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="313" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjfiYzaaYINXp-aDaSysFP3Z3ayNTK74YHnIiA6bz_6TUdKTId58wEEFtn5eXS44wIwnNAK6ycAzeLRd3g8k18glLYHVHxJrIRr5ZIwsUHDr9MBV7ZE0_VGG-m1sMyJ2H3kvKkqn4FmAO4E/s640/gen_pass_python.png" width="640" /></a></div>
Here is an example of password generated with this code : "THQ>Y83Lq*.6d". This password is a secure password.<br />
<br />
The entropy of the password :<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEheDlJDPu62JNxnIWkTI0JuQ6U6_4tSkaTG3uzLXQcPwlvKYt6Qu3G8RcgdnD_hTQi7pKTo5-iAHkayUiIpHwjtFBb68mdPsQtEovNQntPCtNi51IeRG18FKx3TknpKbA_ooWGhaVHxXm2j/s1600/entropy_secure_password.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEheDlJDPu62JNxnIWkTI0JuQ6U6_4tSkaTG3uzLXQcPwlvKYt6Qu3G8RcgdnD_hTQi7pKTo5-iAHkayUiIpHwjtFBb68mdPsQtEovNQntPCtNi51IeRG18FKx3TknpKbA_ooWGhaVHxXm2j/s1600/entropy_secure_password.png" /></a></div>
But this one is really difficult to learn and you will write it on a post-it. Doing that your system will be compromised by your<br />
colleagues or the housekeeper. The password should be easy to learn!<br />
An example to generate a good password, with the same entropy, is to take your favorite sentence and to translate it into a password :<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiRUpD3gsZIBfojb3LxdOkXvYiHwTzoacqBGpx9Yh8XWurBqOevuDfefWKJCoiHNZcFCBYv6KnxWw1XQt9J31jdk0QHW0B7Izi9dMHcREgK9EGmm70hrT_Va_xoby8ib7QAmsnceqSdG9lD/s1600/translate_pwd.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="65" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiRUpD3gsZIBfojb3LxdOkXvYiHwTzoacqBGpx9Yh8XWurBqOevuDfefWKJCoiHNZcFCBYv6KnxWw1XQt9J31jdk0QHW0B7Izi9dMHcREgK9EGmm70hrT_Va_xoby8ib7QAmsnceqSdG9lD/s640/translate_pwd.png" width="640" /></a></div>
You can also mix between uppercase and lowercase, take a letter every 3 letters and so on. It's easy to learn this password, the charset used is :<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj9AJo-7cZSHnTgktBCBqCbNM-PPQxfVXyZZuhSHPBvUnpbYTq1NXDdNo8YKjlR9g3tCJG3US61LcnQEePk7kUoWrhHe_K7GpTjcwQ74_jdKiD335NnwEEXHhe917mA7fTmpWg-WotMKWrs/s1600/new_charset.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="40" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj9AJo-7cZSHnTgktBCBqCbNM-PPQxfVXyZZuhSHPBvUnpbYTq1NXDdNo8YKjlR9g3tCJG3US61LcnQEePk7kUoWrhHe_K7GpTjcwQ74_jdKiD335NnwEEXHhe917mA7fTmpWg-WotMKWrs/s400/new_charset.png" width="400" /></a></div>
The entropy of the password :<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjb-0eV3HrWzmf2oEpO7Z1oKPl1aOCGE_-mD7c5fQond6LmJMw0ETrgtXde-D-aZmn7nH9Wzu9ZTo08P8gPnb7c1huZfDR_izgl1h3LhIJbHdaeN3b5aAL25lrna9_ypwLszWr-ddMT73I7/s1600/entropy_easy_to_learn_pwd.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjb-0eV3HrWzmf2oEpO7Z1oKPl1aOCGE_-mD7c5fQond6LmJMw0ETrgtXde-D-aZmn7nH9Wzu9ZTo08P8gPnb7c1huZfDR_izgl1h3LhIJbHdaeN3b5aAL25lrna9_ypwLszWr-ddMT73I7/s1600/entropy_easy_to_learn_pwd.png" /></a></div>
The entropy of this "easy to learn" password is even superior of our complicated password. We did a lot of suppositions like taking a minimal charset to compute<br />
the entropy, and even with these suppositions this password is better! The scheme of this password is really difficult to predict, that's why it's a good password.<br />
If you have no information about the password it will be really difficult to break it!<br />
<br />
<b><span style="font-size: x-large;">Conclusion</span></b><br />
<br />
To conclude, we saw that it's easy to break weak passwords. A weak password is a password with a small length and with low entropy. We saw that we can use "strategies" to speed up our brute-force, and even passwords of "10" characters length with predictable schemes are breakable. It's just a story of entropy. We also saw what is a good password and how to learn it easily.</div>
kutiohttp://www.blogger.com/profile/17775395880749568836noreply@blogger.com3tag:blogger.com,1999:blog-1388118120443170895.post-81802910676385948282011-12-28T05:23:00.000-08:002013-06-08T02:36:28.670-07:00libLLL<div dir="ltr" style="text-align: left;" trbidi="on">
Hello world!<br />
<br />
For my first post, I want to share a small library that I developed during my spare time : libLLL !<br />
<br />
The first idea of this library was initially to solve the knapsack problem of the SecurIMAG's challenge 5 (<a href="http://ensiwiki.ensimag.fr/index.php/Portail:SecurIMAG_Ensimag_IT_security_club/Challenges"> Easy for Santa Claus and his helpers</a> by Mirak ). I didn't find an implementation in Python of the LLL algorithm ( Arjen Lenstra, Hendrik Lenstra and László Lovász ). <span class="" id="result_box" lang="en"><span class="hps">Usually</span> <span class="hps">I use</span> PARI/GP <span class="hps">and</span> <span class="hps atn">the "</span><span class="">qflll</span>" function <span class="hps">to reduce my</span> <span class="hps">lattices, </span></span><span class="" id="result_box" lang="en"><span class="hps">but this time</span> <span class="hps">I wanted to</span> <span class="hps">integrate</span> <span class="hps">the lattice reduction</span><span class="hps"> in</span> <span class="hps">my</span> <span class="hps">Python</span> <span class="hps">scripts</span> <span class="hps">to automate the</span> <span class="hps">whole.</span></span><br />
<br />
<span class="" id="result_box" lang="en"><span class="hps">I'm not</span> <span class="hps">a</span> <span class="hps">pure</span> <span class="hps">m</span></span><span class="" id="result_box" lang="en"><span class="hps">athematici</span></span><span class="" id="result_box" lang="en"><span class="hps">an,</span> <span class="hps">so I</span> <span class="hps">will not go into</span> <span class="hps">the theory to explain in detail what is formally a lattice and to prove the LLL algorithm. In this post I just propose an implementation of the LLL algorithm in Python and explain how to use it to break the Merkle Hellman cryptosystem. If you are interested by the theory I encourage you to buy the book "The LLL Algorithm : Survey and Applications" by Phong Q.Nguyen and Brigitte Vallée.</span></span><br />
<span class="" id="result_box" lang="en"><span class="hps"><br />
</span></span><br />
<span class="" id="result_box" lang="en"><span class="hps">In one hand I will explain the Merkle Hellman knapsack cryptosystem, in second hand I will explain how to use liblll to break the </span></span><span class="" id="result_box" lang="en"><span class="hps">Merkle Hellman knapsack cryptosystem and finally I will show how to use libLLL to break the "</span></span>Easy for Santa Claus and his helpers" challenge.<br />
<br />
<a name='more'></a><br />
<span style="font-size: large;"><u><b><span class="" id="result_box" lang="en"><span class="hps"></span></span><span class="" id="result_box" lang="en"><span class="hps">Merkle Hellman knapsack cryptosystem</span></span></b></u></span><br />
<span style="font-size: large;"><u><b><span class="" id="result_box" lang="en"><span class="hps"><br />
</span></span></b></u></span><br />
<span class="" id="result_box" lang="en"><span class="hps">The Merkle/Hellman knapsack cryptosystem is an asymetric cryptosystem.</span></span><br />
<br />
<a href="http://4.bp.blogspot.com/-ThPUGt_v0GY/TvrwvrNALMI/AAAAAAAAAB4/IWWUSDcz0Hs/s1600/merkle_hellman_knapsack_cryptosystem.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="155" src="http://4.bp.blogspot.com/-ThPUGt_v0GY/TvrwvrNALMI/AAAAAAAAAB4/IWWUSDcz0Hs/s640/merkle_hellman_knapsack_cryptosystem.png" width="640" /></a><span class="" id="result_box" lang="en"><span class="hps">Examples of knapsack :</span></span><br />
<span class="" id="result_box" lang="en"><span class="hps"><br />
</span></span><br />
<b><span class="" id="result_box" lang="en"><span class="hps">An easy one :</span></span></b><br />
<span class="" id="result_box" lang="en"><span class="hps"><br />
</span></span><br />
<span class="" id="result_box" lang="en"><span class="hps">a = [37, 98, 23, 29 ]</span></span><br />
<span class="" id="result_box" lang="en"><span class="hps">t = 127</span></span><br />
<span class="" id="result_box" lang="en"><span class="hps"><br />
</span></span><br />
<span class="" id="result_box" lang="en"><span class="hps">with this example it's easy to see that x = [0, 1, 0, 1 ]</span></span><br />
<span class="" id="result_box" lang="en"><span class="hps"><br />
</span></span><br />
<span class="" id="result_box" lang="en"><span class="hps">because 98 + 29 = 127</span></span><br />
<span class="" id="result_box" lang="en"><span class="hps"><br />
</span></span><br />
<b><span class="" id="result_box" lang="en"><span class="hps">A more complicated one :</span></span></b><br />
<span class="" id="result_box" lang="en"><span class="hps"><br />
</span></span><br />
<span class="" id="result_box" lang="en"><span class="hps">a = [964266105338945, 6749864515101946, 964264861986975, 13499727318176232, 17356789956975810,3857053002628327, 12535438500695219, 10606879723866753, 10606828405887831, 16392324024362666, 13499318722439347, 7713307812454905, 6748217527825207, 6746569486347068, 8671806553725916, 2879615947706164, 18294696345811439, 6697131932913639, 15322796985338016, 753333165640954, 16934930158297044, 10727464396496856, 8919464717468072, 12053330796850461]</span></span><br />
<span class="" id="result_box" lang="en"><span class="hps"><br />
</span></span><br />
<span class="" id="result_box" lang="en"><span class="hps">t = 85665597416613316</span></span><br />
<span class="" id="result_box" lang="en"><span class="hps"><br />
</span></span><br />
<span class="" id="result_box" lang="en"><span class="hps">With a such knapsack, it's more complicated to guess the solution. You have to use a computer! </span></span><br />
<span class="" id="result_box" lang="en"><span class="hps"><br />
</span></span><br />
<span class="" id="result_box" lang="en"><span class="hps">The first idea to break this knapsack is to try all the combinations until the sum is equal to </span></span><span class="" id="result_box" lang="en"><span class="hps">85665597416613316. If you do a naive brute force algorithm, you will make about 2^24 computations ( easy with a personal computer ). You can also speed up the computation using "<a href="http://en.wikipedia.org/wiki/Knapsack_problem">dynamic programming</a>".</span></span><br />
<span class="" id="result_box" lang="en"><span class="hps"><br />
</span></span><br />
<span class="" id="result_box" lang="en"><span class="hps">Fortunately, the knapsack problem can be modelized using lattices!</span></span><br />
<span class="" id="result_box" lang="en"><span class="hps"><br />
</span></span><br />
<span style="font-size: large;"><u><b><span class="" id="result_box" lang="en"><span class="hps">LLL algorithm / Lattices</span></span></b></u></span><br />
<span style="font-size: large;"><u><b><span class="" id="result_box" lang="en"><span class="hps"><br />
</span></span></b></u></span><br />
The knapsack problem can be solved using the LLL algorithm, consider a knapsack problem :<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://2.bp.blogspot.com/-QTI4gGHSrBk/Tvr50THgr9I/AAAAAAAAACE/jDi_t3lS4rc/s1600/knapsack_problem.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="30" src="http://2.bp.blogspot.com/-QTI4gGHSrBk/Tvr50THgr9I/AAAAAAAAACE/jDi_t3lS4rc/s320/knapsack_problem.png" width="320" /></a></div>
For our previous easy example , the lattice modeling this problem is this one :<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/-3EVETb4YkBQ/Tvr72ZlNPPI/AAAAAAAAACQ/4tfsOVVsuEQ/s1600/easy_lattice.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-3EVETb4YkBQ/Tvr72ZlNPPI/AAAAAAAAACQ/4tfsOVVsuEQ/s1600/easy_lattice.png" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/-LUtajK_AT1Y/Tvr-LYwm_hI/AAAAAAAAACc/Z79Nnr8MgTo/s1600/vector_lattice.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="28" src="http://1.bp.blogspot.com/-LUtajK_AT1Y/Tvr-LYwm_hI/AAAAAAAAACc/Z79Nnr8MgTo/s640/vector_lattice.png" width="640" /></a></div>
By construction , v is a short vector of L, thus we can hope to find it using LLL algorithm ( see Shortest Vector Problem and Closest Vector Problem of the LLL book for more information ).<br />
<br />
libLLL implements the LLL algorithm, so we can find this shortest vector! It's not an easy task to find a not buggy pseudocode LLL algorithm on Internet.<br />
<br />
The pseucode used for the implementation :<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/-J9eQD-cF_7M/TvsIEXIRAII/AAAAAAAAACo/iyZJcz6THQA/s1600/lll_algorithm_pseudocode.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="640" src="http://1.bp.blogspot.com/-J9eQD-cF_7M/TvsIEXIRAII/AAAAAAAAACo/iyZJcz6THQA/s640/lll_algorithm_pseudocode.png" width="585" /></a></div>
<br />
<b>Break </b><span class="" id="result_box" lang="en"><span class="hps"><b>a = [37, 98, 23, 29] , t = 127 :</b></span></span><br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://3.bp.blogspot.com/-xeTFEm-fpzg/TvsKo6pGSAI/AAAAAAAAAC0/oUuo2T0-Ym0/s1600/break_easy_example_liblll.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="227" src="http://3.bp.blogspot.com/-xeTFEm-fpzg/TvsKo6pGSAI/AAAAAAAAAC0/oUuo2T0-Ym0/s640/break_easy_example_liblll.png" width="640" /></a></div>
<span class="" id="result_box" lang="en"><span class="hps"><br />
</span></span><br />
<span class="" id="result_box" lang="en"><span class="hps">Thus the solution is [0, 1, 0, 1], let's try with the more complicated example :) :</span></span><br />
<span class="" id="result_box" lang="en"><span class="hps"><br />
</span></span><br />
<b><span class="" id="result_box" lang="en"><span class="hps">Break the complicated example :</span></span></b><br />
<br />
<span class="" id="result_box" lang="en"><span class="hps">a = [964266105338945, 6749864515101946, 964264861986975, 13499727318176232, 17356789956975810,3857053002628327, 12535438500695219, 10606879723866753, 10606828405887831, 16392324024362666, 13499318722439347, 7713307812454905, 6748217527825207, 6746569486347068, 8671806553725916, 2879615947706164, 18294696345811439, 6697131932913639, 15322796985338016, 753333165640954, 16934930158297044, 10727464396496856, 8919464717468072, 12053330796850461]</span></span><br />
<span class="" id="result_box" lang="en"><span class="hps"><br />
</span></span><br />
<span class="" id="result_box" lang="en"><span class="hps">t = 85665597416613316</span></span><br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/-LN5w7gpBz8A/TvsNHTF_u6I/AAAAAAAAADU/lnHdGudfIbo/s1600/break_complicated_example_liblll.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="264" src="http://1.bp.blogspot.com/-LN5w7gpBz8A/TvsNHTF_u6I/AAAAAAAAADU/lnHdGudfIbo/s640/break_complicated_example_liblll.png" width="640" /></a></div>
<br />
<span class="" id="result_box" lang="en"><span class="hps">Thus the solution is [0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0] :) !</span></span><br />
<br />
<span class="" id="result_box" lang="en"><span class="hps"><br />
</span></span><br />
<span style="font-size: large;"><u><b><span class="" id="result_box" lang="en"><span class="hps">Easy for santa claus and his helpers</span></span></b></u></span><br />
<br />
<span class="" id="result_box" lang="en"><span class="hps">The parameters of the challenge :</span></span><br />
<span class="" id="result_box" lang="en"><span class="hps"><br />
</span></span><br />
a = [964266105338945, 6749864515101946, 964264861986975, 13499727318176232, 17356789956975810, 3857053002628327, 12535438500695219, 10606879723866753, 10606828405887831, 16392324024362666, 13499318722439347, 7713307812454905, 6748217527825207, 6746569486347068, 8671806553725916, 2879615947706164, 18294696345811439, 6697131932913639, 15322796985338016, 753333165640954, 16934930158297044, 10727464396496856, 8919464717468072, 12053330796850461]<br />
<br />
t[] = [85665597416613316, 68924182376697138, 93855260302436631, 67069112787809230, 67823425594155918, 96038092151406072, 88581012026674643, 87131275443855194, 92447984720405935, 78684146336120268, 52303820625741832, 85294112192719803, 48802767159478973, 93706609509995531, 143147771785836836, 79544023096864593, 118984178180084169, 66881447736363380, 83048004789685724]<br />
<br />
So to uncipher the ciphertext we just have to break the knapsack problem for each t[i]. Doing that we can obtain the binary of the plaintext !<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://4.bp.blogspot.com/-uQiCRDMPISQ/TvsQHuBni6I/AAAAAAAAADg/ZnssIe9ROxc/s1600/challenge_5.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="412" src="http://4.bp.blogspot.com/-uQiCRDMPISQ/TvsQHuBni6I/AAAAAAAAADg/ZnssIe9ROxc/s640/challenge_5.png" width="640" /></a></div>
<br />
<span style="font-size: large;"><u><b><span class="" id="result_box" lang="en"><span class="hps">Conclusion</span></span></b></u></span><br />
<br />
Now you can easily break knapsack problem and reduce lattices in python using libLLL ! I do not guarantee that there is no bug in the LLL algorithm but this one "seems" to work, if you find bugs/problems you can send me emails at kutioo [.at.] gmail [.dot.] com. libLLL is GPL v3, so you can be part of the project. The repository is here : <a href="https://github.com/kutio/liblll/">libLLL</a>. All the examples in this article are available on the git repository ! I'm beginner in python, thus if you find "optimizations" to speed up the reduction algorithm don't hesitate !<br />
<a href="https://github.com/kutio/liblll/"></a><br />
<a href="https://github.com/kutio/liblll/"></a><br />
<b>greetz : Mirak and PEV</b><br />
<span style="font-size: large;"><u><b><span class="" id="result_box" lang="en"><span class="hps"><br />
</span></span></b></u></span></div>
kutiohttp://www.blogger.com/profile/17775395880749568836noreply@blogger.com2