Mostrando entradas con la etiqueta Seguridad y Criptografía. Mostrar todas las entradas
Mostrando entradas con la etiqueta Seguridad y Criptografía. Mostrar todas las entradas

martes, 30 de octubre de 2012

[SC] 9. Steganography

For this week the challenge was implement a steganography script using python, so, here are my pictures.

This one contain a hidden message:


Hidden Plaintext:

CHAPTER I.
WHICH TREATS OF THE CHARACTER AND PURSUITS OF THE FAMOUS GENTLEMAN DON QUIXOTE OF LA MANCHA

In a village of La Mancha, the name of which I have no desire to call to mind, there lived not long since one of those gentlemen that keep a lance in the lance-rack,
an old buckler, a lean hack, and a greyhound for coursing. An olla of rather more beef than mutton, a salad on most nights, scraps on Saturdays, lentils on Fridays,
and a pigeon or so extra on Sundays, made away with three-quarters of his income. The rest of it went in a doublet of fine cloth and velvet breeches and shoes to match
for holidays, while on week-days he made a brave figure in his best homespun. He had in his house a housekeeper past forty, a niece under twenty, and a lad for the field
and market-place, who used to saddle the hack as well as handle the bill-hook. The age of this gentleman of ours was bordering on fifty; he was of a hardy habit, spare,
gaunt-featured, a very early riser and a great sportsman. They will have it his surname was Quixada or Quesada (for here there is some difference of opinion among the
authors who write on the subject), although from reasonable conjectures it seems plain that he was called Quexana. This, however, is of but little importance to our tale;
it will be enough not to stray a hair's breadth from the truth in the telling of it.

You must know, then, that the above-named gentleman whenever he was at leisure (which was mostly all the year round) gave himself up to reading books of chivalry with
such ardour and avidity that he almost entirely neglected the pursuit of his field-sports, and even the management of his property; and to such a pitch did his eagerness
and infatuation go that he sold many an acre of tillageland to buy books of chivalry to read, and brought home as many of them as he could get. But of all there were none
he liked so well as those of the famous Feliciano de Silva's composition, for their lucidity of style and complicated conceits were as pearls in his sight, particularly
when in his reading he came upon courtships and cartels, where he often found passages like "the reason of the unreason with which my reason is afflicted so weakens my
reason that with reason I murmur at your beauty;" or again, "the high heavens, that of your divinity divinely fortify you with the stars, render you deserving of the
desert your greatness deserves." Over conceits of this sort the poor gentleman lost his wits, and used to lie awake striving to understand them and worm the meaning out
of them; what Aristotle himself could not have made out or extracted had he come to life again for that special purpose. He was not at all easy about the wounds which
Don Belianis gave and took, because it seemed to him that, great as were the surgeons who had cured him, he must have had his face and body covered all over with seams
and scars. He commended, however, the author's way of ending his book with the promise of that interminable adventure, and many a time was he tempted to take up his pen
and finish it properly as is there proposed, which no doubt he would have done, and made a successful piece of work of it too, had not greater and more absorbing thoughts
prevented him.

Three of these ones (the three inside the blue frame) contains the python code used to hide the information:







So, let's hack begin...

Code:

To download the code:


To download the images:

  
To encode information:

python stegano.py -E

To decode information

python stegano.py  -D

Then, enter the requested data.



jueves, 25 de octubre de 2012

[SC] 8. Stream ciphers: Grain

Introduction


Grain is a stream cipher pruposed and submitted to eSTREAM project by Martin Hell, Thomas Johansson and Willi Meier in 2004.It has been selected for the final eSTREAM portfolio for Profile 2 by the eSTREAM project.

Grain is designed for very restricted hardware environments, such as RFID tags.

The cipher is based on Linear Feedback Shift Register (LFSR) and non-linear feedback shift register (NFSR).

Background



Actually exists a need of cryptographic systems that have a low hardware complexity. Per example, a RFID tag has a very limited amount of resources; it's a microchip capable of transmiting a sequence after a request from the reader.


There are serveral aplications for RFID tags, mostly, card-based authentication systems. The information transmitted between the card and the readers can be hacked easily because there isn't a system that protects the information during its transmission.

Devasting consequences could happen if the RFID tags were implemented, seriously, in electronic payments and hence.


Today, the implementation of AES and DES on an RFID tag is not feasible due to the expensive hardware cost (the large number of logical gates, gate equivalent).
And we can take so much more other examples, such as, bluetooth and NFC modules, microchips, sim cards, memory cards, etc.
Grain is a stream cipher designed to be very simple and small to implement in hardware.

Grain provides a higher security than other ciphers intended to be used in hardware applications, such as E0 used in Bluetooth and A5/1 used in GSM.
These ciphers, while also having a very small hardware implementation, have been proven to be very insecure.
Compared to E0 and A5/1, Grain provides higher security while maintaining a small hardware complexity.

Specification


Grain is based in three main blocks:
  • A 80-bit linear feedback shift register
  • A 80-bit nonlinear feedback shift register
  • A nonlinear filtering function. 

Grain is initialized with the 80-bit key K and the 64-bit initialization value IV . The cipher output is an L-bit keystream sequence (zt) t = 0,...,L−1.

The current LFSR content is denoted by St+80 = (st, st+1, . . . , st+79).

The feedback polynomial of the LFSR, f(x) is a primitive polynomial of degree 80. It is defined as:

f(x) = 1 ⊕ x18 ⊕ x29 ⊕ x42 ⊕ x57 ⊕ x67 ⊕ x80

The update function of LFSR is governed by the linear recurrence:

st+80 = st+62 ⊕ st+51 ⊕ st+38 ⊕ st+23 ⊕ st+13 ⊕ st


The current NFSR content is denoted by Bt+80 = (bt, bt+1, . . . , bt+79).
The feedback polynomial of the NFSR, g(x), is defined as:

g(x) = 1 ⊕ x17 ⊕ x20 ⊕ x28 ⊕ x35 ⊕ x43 ⊕ x47 ⊕ x52 ⊕ x59 ⊕ x65 ⊕ x71 ⊕ x80 ⊕ x17x20 ⊕ x43x47 ⊕ x65x71 ⊕ x20x28x35 ⊕ x47x52x59 ⊕ x17x35x52x71 ⊕ x20x28x43x47 ⊕ x17x20x59x65 ⊕ x17x20x28x35x43 ⊕ x47x52x59x65x71 ⊕ x28x35x43x47x52x59

 The NFSR feedback is disturbed by the output of the LFSR, so that the NFSR content is governed by the recurrence:

bt+80 = st ⊕ g(bt, bt+1, . . . , bt+79)

where:

g(bt, bt+1, . . . , bt+79) = bt+63 ⊕ bt+60 ⊕ bt+52 ⊕ bt+45 ⊕ bt+37 ⊕ bt+33 ⊕ bt+28⊕ bt+21 ⊕ bt+15 ⊕ bt+9 ⊕ bt ⊕ bt+63bt+60 ⊕ bt+37bt+33 ⊕ bt+15bt+9 ⊕ bt+60bt+52bt+45 ⊕ bt+33bt+28bt+21 ⊕ bt+63bt+45bt+28bt+9 ⊕ bt+60bt+52bt+37bt+33 ⊕ bt+63bt+60bt+21bt+15 ⊕ bt+63bt+60bt+52bt+45bt+37 ⊕ bt+33bt+28bt+21bt+15bt+9 ⊕ bt+52bt+45bt+37bt+33bt+28bt+21


The contents of the two shift registers represent a state of the cipher. The cipher output bit is derived from these states; 5 variables (x0, x1, x2, x3, x4) are taken as input to a boolean function, h(x), the bits are st+3, st+25, st+46, st+64 and bt+63

This filter function is chosen to be balanced, correlation immune of the first order and has algebraic degree 3. The function is defined as:

h(x) = x1 ⊕ x4 ⊕ x0x3 ⊕ x2x3 ⊕ x3x4 ⊕ x0x1x2 ⊕ x0x2x3 ⊕ x0x2x4 ⊕ x1x2x4 ⊕ x2x3x4

Finally, we take take the output of the NFSR and the output of h(x), apply xor with both values to obtain a bit of the keystream.

The  keystream is combined with the plaintext using XOR operation to obtain ciphertext.



Key Initialization

Before generate a keystream, the cipher must be initialized with the key and an iniatialization vector (IV), the process as the follows:
  • Put the 80-bit length key in the NFSR
  • Put the 64-bit length IV in LFSR
  • Fill the remaining 16 bits of the LFSR with ones.
  • Clock the cipher at 160 cycles.
  • Run the cipher.
  • The output of the cipher must be xored with the input of both NFSR and LFSR.




Vulnerabilities and proposed solutions



From "Grain - A Stream Cipher for Constrained Environments"


    There are several vulnerabilities found in Grain cipher, such as:

    • "Correlations: Due to the statistical properties of maximum-length LFSR sequences, the bits in the LFSR are (almost) exactly balanced. This may not be the case for a NFSR when it is driven autonomously. However, as the feedback g(x) is xored with a LFSR-state, the bits in the NFSR are balanced. Moreover, recall that g is a balanced function. Therefore, the bits in the NFSR may be assumed to be uncorrelated to the LFSR bits. The function h is chosen to be correlation immune of first order. This does not preclude that there are correlations of the output of h(x) to sums of inputs. As one input comes from the NFSR and as h(x) is xored with a state bit of the NFSR, correlations of the output of the generator to sums of LFSR-bits will be so small that they will not be exploitable by (fast) correlation attacks."


    • "Algebraic Attack: A filter generator alone with output function h(x) of degree only three would be very vulnerable to algebraic attacks. On the other hand, algebraic attacks will not work for solving for the initial 160-bit state of the full generator, as the update function of the NFSR is nonlinear, and the later state bits of the NFSR as a function of the inital state bits will have varying but large algebraic degree. Using key initialization, it may be possible to express the output of the generator as a function of state bits of the LFSR alone. As the filter function h(x) has one input coming from the NFSR, and h(x) is xored with a NFSR-state bit, the algebraic degrees of the output bits when expressed as a function of LFSR-bits, are large in general, and varying in time. This will defeat algebraic attacks."


    • "Time/Memory/Data Tradeoff Attack: The cost of time/memory/data tradeoff attacks on stream ciphers is O(2n/2), where n is the number of inner states of the stream cipher. To obey the margins set by this attack, n = 160 has been chosen. It is known that stream ciphers with low sampling resistance have tradeoff attacks with fewer table lookups and a wider choice of parameters. The sampling resistance of h(x) is reasonable:
      • This function does not become linear in the remaining variables by fixing less than 3 of its 5 variables. Similarly, the variables occuring in monomials of g(x) are sufficiently disjoint. Hence the resulting sampling resistance is large, and thus time/memory/data tradeoff attacks are expected to have complexity not lower than O(280)."



    References



    jueves, 18 de octubre de 2012

    [SC] 7. Block Ciphers: PRESENT

    Introduction


    PRESENT cipher was developed together by the Orange Labs in France, The Ruhr University Bochum in Germany and the Technical University of Denmark; and was first published on August 23 of 2007.

    PRESENT cipher is one of the most compact encryption methods ever designed and is 2.5 times smaller than AES (Advanced Encryption Standard).

    The specifications of PRESENT cipher was written in the paper "PRESENT: An Ultra-Lightweight Block Cipher", published in 2007 in the event CHES 2007 (Cryptographic Hardware and Embedded Systems Workshop) in Vienna, Austria , the authors are:
    • A. Bogdanov, G. Leander and C. Paar from Horst-Görtz-Institute for IT-Security at Ruhr-University Bochum in Germany
    • A. Poschmann, L.R. Knudsen and C. Vikkelsoe from Technical University Denmark at Lyngby, Denmark
    • M.J.B. Robshaw and Y. Seurin from France Telecom R&D at Issy les Moulineaux, France

    Background


    Actually the computation paradigm are shifting to Pervasive Computing, so, there are a lot of devices with a limited amount of CPU, memory, power, and energy consumption. The problem is that all known ciphers are designed for high performance devices.

    The goals of the PRESENT cipher are:
    • The cipher is to be implemented directly in the hardware, efficiently
    • Applications with moderate security levels (80 bit)
    • Small amounts of encrypted data
    • Often no rekeying possible (Encryption only core)
    • Metrics:
      • Security
      • Power consumption
      • Time
    That means that in very small devices such as RFID cards or microcontrollers is possible to implement a cipher for simple security tasks, that with other ciphers was not possible due to the system requirements.

    Some concepts

    Specification


    The PRESENT cipher is a simple SP-network with 64-bits block size and 80 or 128 bits of key lenght (PRESENT128 for the 128 bit version). A key lenght of 80-bits provides a good security level for many RFID or other small applications.

    PRESENT uses a round-based algorithm, 32 rounds in total, where 31 rounds are regular rounds that consists in a key mixing step, a substitution layer and a permutation layer; the final round consists only in the key mixing step.

    The recommended functions are:
    • addRoundKey: Given round key Ki = [K63, K62, ..., K1, K0], and a current state bi = [b63, b62, ..., b1, b0]; the key mixing step addRoundKey consists in a XOR operation:
    bj = bj ⊕ Kj; for j ≤ 0 ≤ 63

    • sBoxLayer: The S-box used in PRESENT is a 4-bit to 4-bit S-box, the 64-bit block is divided in chunks of 4-bits, each 4-bit chunk is the input to a S-box. The S-Box Layer consist in 16 parallel S-boxs. The substitutions, written in hexadecimal (1111 = F) are given by the following table:

    • pLayer: Performs a bit permutation, where the bit i of the block is moved to bit position P(i).  The permutation used in PRESENT is given by the following table.


    • keyRegisterUpdate: The key register stores a 80-bit key, where, only the 64 leftmost bits are used in the key mixing step. After that, the key register is updated, the key register is rotated 61-bits to the left, the left-most four bits are passed through the present S-box, finally the round counter is XOR-ed with the bits 15-19 of the key register. 

    The whole SP-Network of PRESENT cipher is represented as follows:


    Finally, the pseudocode algorithm and flow diagram are represented as follows:



    Example (v0.1)

    For this report I was trying to write my own implementation of PRESENT in python, but, something went wrong, as you can see in the following picture.



    Basically, I have 2 errors:
    • The implementation only accept numeric strings.
    • The implementation only decode the last 2 characters of the string
    I think there are some errors in my conversion logic because I need to convert the strings from bin to hex to ascii and viceversa, so, maybe the encrypt-decrypt engine is half ok.

    I will update this entry when the code is ready, sorry for my failure.

    In the references (bottom) are some implementations of PRESENT in C and Python.

    Vulnerability


    An example of vulnerability in PRESENT cipher is the Statistical Saturation Attack. The attack is based on a weakness in the permutation layer of PRESENT. 
    This weakness can be found making a closer look to the permutation layer, in this example, the S-boxes 5,6,9 and 10 (counting from S-box 0 at the right), only 8 out of 16 input bits are directed to other S-boxes, and the other 8 input bits are fixed in all rounds!.

    Permutation Layer Poor Diffusion example 1, from "A Statistical Saturation Attack against the Block Cipher PRESENT"



    There are many other examples of poor diffusion in the permutation. So, if the 16 bits at the input of the S-boxes 5-6-9-10 are fixed, then 8 bits will be known at the very same input for the next round. We can iteratively repeat this process round by round and observe a non-uniform behavior at the output of the S-boxes 5-6-9-10.

    The attack 
    from: "A Statistical Saturation Attack against the Block Cipher PRESENT"

    "In order to exploit this weakness, we first evaluate theoretically the distribution of the 8 bits in the bold trail of the above picture at the output of the S-box layer, for a fixed value of the same 8 bits of plaintext. This requires to guess the 8 subkey bits involved in the trail. One also needs to assume that the bits not situated in the trail are uniformly distributed. This is a reasonable assumption as soon as the 56 remaining bits of plaintext (excluding the 8 bits in the trail) are randomly generated. Then, given the distribution of the 8-bit trail at the input of a round, it is possible to compute the 8-bit distribution at the output of the round. Iteratively, we can compute the distribution for an arbitrary number of rounds.
    For each key guess, the work needed to compute the theoretical distribution of the target trail after r rounds is equivalent to r · 216 partial encryptions.

    Once we have computed the theoretical distributions of the trail for each possible key guess, we can attack the cipher by simply comparing them with a practical distribution obtained by encrypting a large number of plaintexts with a secret key. The key guess minimizing the distance between theoretical and practical distributions is chosen as the correct key. We can construct a list of key candidates sorted according to the distance between theory and practice. The better the position of the right key in the list, the better the attack."

    Permutation Layer Poor Diffusion example 2, from "A Statistical Saturation Attack against the Block Cipher PRESENT"



    Referencias

    http://www.lightweightcrypto.org/present/present_cardis2008.pdf
    http://www.lightweightcrypto.org/present/present_ches2007.pdf
    http://www.emsec.rub.de/media/crypto/veroeffentlichungen/2011/01/29/present_ches2007_slides.pdf
    http://homes.esat.kuleuven.be/~abogdano/talks/present_rfidsec07.pdf
    http://math.fau.edu/~eisenbarth/pdf/SLEsolvers.pdf

    http://www.lightweightcrypto.org/implementations.php

    miércoles, 19 de septiembre de 2012

    [SC] 6. RSA-Based Digital Signatures

    For this week the homework was:

    "Implement a HTTP public key repository for ket exchange that employs RSA-bases digital signatures"

    Implementation


    The deployed web application uses a python script as CGI to serve the request, and another script named validator, to validate the written data into the forms.

    The CGI implements 

    • def function(x): The function that is evaluated with x, returns the value of fx.
    • def fastmodexp(r, e, n): Calculates the value of y (y = re mod n)
    • def generateResult(x, username, r): When the CGI validates the values of x, username and response, this function uses the username to get the value of e and n, then, calculates the value of fx and y, finally, compares their values and if fx and y are equals returns SUCCESS!, otherwise, returns FAILURE!. Implements a debug flag to print all the calculated values.
    • def validation(): Validates that the written data in the forms has the correct format. Uses a error flag to warn to the script if something is wrong, then, prints the error messages.
    • def getOption(): Gets the option of the CGI form. If option doesn't exists in the form, the normal page is printed. If option exists in the form and the value is one, the CGI generate a challenge value and print it in the challenge input. If the value is two, the CGI gets the value of the challenge, username and response inputs and send them to the validate function.
    • def getUsers(): Open the text file with the users data (public keys), read the contents and parse them to a list. Return a list with all the users and keys.
    • def getUserData(username): Read the list of users and extract the data of the specified username.
    • def generateChallenge(): Implements random.randint to generate a challenge between a specified range.
    • def printUsers(selectedUser): Prints the select input in the web page, calls the function getUsers(), gets the list of users and uses the information to generate options. Uses the parameter selectedUser to print a preselected option.
    • def printHead(challenge, selectedUser, response, result): Prints all the web application. If challenge is defined, prints its value in the challenge input. If selectedUser is defined, send it to the function printUsers() to print the select input with a preselected username. If response is defined, prints its value in the response input. If result is defines, prints its contents (error messages or successful messages) in a hidden specified area below the response input.
    • def main(): Gets the form, search for the option key and makes a decision to print the correct content in the window.
    Also implements JQuery to control the events of the buttons and manage dynamically the form values.

    Code - webapp



    Script

    The user has to download a script to generate the response, the script implements the functions :
    • def function(x): The function that is evaluated with x, returns the value of y.
    • def fastmodexp(y, d, n): Calculates the value of r (r = yd mod n)
    The user must copy and paste the response in the webapp to validate the data.

    Code - script



    External Tests

    Cecy


    Web Interface

     Script Execution






    Ramon

    Web Interface

    Rafael





    Web Interface



     Script Execution


    Video


    http://www.youtube.com/watch?v=qFQEJK2cZ8A


    Link to the WebApp

    http://jcespinosa.dyndns-web.com/~jc1/cgi-bin/cryptography/authentication.py

    jueves, 13 de septiembre de 2012

    [SC] 5. RSA Authentication

    For this homework, we have to implement the RSA Authentication in python for a client-server system using sockets.

    Introduction


    RSA is an algorithm for public-key cryptography that is based on the presumed difficulty of factoring large integers, the factoring problem. RSA stands for Ron Rivest, Adi Shamir and Leonard Adleman, who first publicly described it in 1977. Clifford Cocks, an English mathematician, had developed an equivalent system in 1973, but it was classified until 1997. A user of RSA creates and then publishes the product of two large prime numbers, along with an auxiliary value, as their public key. The prime factors must be kept secret. Anyone can use the public key to encrypt a message, but with currently published methods, if the public key is large enough, only someone with knowledge of the prime factors can feasibly decode the message. Whether breaking RSA encryption is as hard as factoring is an open question known as the RSA problem.
    From http://en.wikipedia.org/wiki/RSA_(algorithm)


    The implementation consist in two parts, the key generator and the client-server system.

    Key Generator

    For the RSA Authentication we need two keys, a public key and a private key. The public key can be know to everyone. The private keys is only know by the user. A message encrypted with the public key can only be decrypted with the private key.

    For the Key generator I followed 3 steps:
    • Request an username
    • Generate a key
    • Save (e and n) in a file named public.txt, save (d and n) in a file named private.txt

    The algorithm to generate the keys is as follows:

    1. Generate two different random integers and prime numbers p and q of 4 digits
    2. Calculate n = p * q
    3. Calculate φn = (p - 1)(q - 1)
    4. Generate a random integer e between 1 and φn-1
    5. Use the Extended Euclidean Theorem to calculate GCD(e, φn) and verify if e and φn are coprimes. The Extended Euclidean Theorem returns 3 values
      • x and y are values ​​that satisfy the expresion ax + by = GCD(a,b)
      • a is the result of GCD(a,b)
    6. If a = 1 then e and φn are coprimes and now d = x, where d ≡ e-1 mod(φn)
    7. (For some reason, sometimes the value of d is negative, a while loop convert it in positive adding φn to d )
    8. At this point we have calculated e (public), d (private) and n

    Code

    RSA Authentication


    For this part I wrote a script in python implementing sockets. The programs expect 3 parameters
    • User type, could be -C to client or -S to server.
    • Host direction
    • Port number
    The script creates a server socket and a client socket, the execution of the script is as follows.
    1. Get the 3 parameters, if missing one, close and exit.
    2. If the 3 parameter are defined, according to the parameter 1 the scripts creates a server socket or a client socket.
    3. The server sockets binds the host and port and wait (listen) for a connection. The client takes the host and port and attempt to connect to the server.
    4. If the connection between then server and the client is sucessfull, the server send to the client a random value x. The server calculates the value of F(x) and the client calculates y using the same function as the server.
    5. The client request a username for the authentication. The client search for the client data in the file private.txt. If the user is in the file, the subroutine returns a list containing the username, d and n, otherwise, the routine shows an exception, returns False and the client closes the connection.
    6. The client uses d and n to calculate r = yd mod (n). The calculations involve very large number, so, I wrote a subroutine based in modular exponentiation named Memory Efficient Method.
      • Memory Efficient Method reduce the amount of resources needed to calculate a modulus reducing the operation to n operations, where n = exponent of the modulus. Three parameters are needed: base, exponent and modulus.
      • Starts with x = 1 and n = exponent, then x = (x * base) mod modulus. The operation is repeated n amount of times.

      • def modularPower(base, exponent, modulus):
        c = 1
        for a in range(exponent):
        c = (c * base)%modulus
        return c

    7. With r computed, the client respond to the server with the username and the value of r
    8. The server also search for the user data using the same subroutine as the client. This time the subroutine returns a list containing the usernamee and n.
    9. The server computes y = remod (n).
    10. If the computed value of y is equals to the computed value of F(x) and these values are equals to the y value computed by the client, the server responds "Welcome!!!" to the client indicating that the authentication was passed, otherwise responds "Failure!!!".
    11. The execution ends at this point.
    NOTE**: The values of e, d and n are read directly from the file, so, we need to edit the files containing the keys to cause a failure.

    Code



    Execution Video


    References

    martes, 4 de septiembre de 2012

    [SC] 4. Hacking Diffie-Hellman Protocol


    INTRODUCTION


    "The Diffie-Hellman algorithm was published in 1976 (named after its creators, Whitfield Diffie and Martin Hellman) can stablish a secret key between two machines via an insecure channel and only sending two messages. The resulting secret key can't be discovered by an attacker, even if it gets the two messages sent by the protocol. The main application of this protocol is to agree on a symmetric key with later encrypt communications between two machines.



    The values of "p" and "g" are public and any attacker can know these, but this is not a vulnerability. Although an attacker knew these values and capture the two messages sent between machines A and B, would not be able to figure out the secret key.

    If the value of "p" and "g" are small, is possible to hack the protocol, but current implementations of the Diffie-Hellman protocol uses very large prime numbers, which prevents an attacker to calculate the values of "a" and "b". The "g" need not be large, and in practice its value is 2 or 5."


    Translated from http://www.javiercampos.es/blog/2011/07/22/el-algoritmo-de-diffie-hellman/

    EXCERCISE


    This week we have to hack a Diffie-Hellman protocol used by two classmates (Alice and Bob). They "encrypt" their communication using the following data:

    • p = 31
    • g = 15
    • X = 23
    • Y = 23

    The formulas are:

    • X = gx mod p
    • Y = gy mod p 
    • k = Yx mod p 
    • k = Xy mod p


    So, I have to recover "x", "y", "k".

    For this task, I did a "brute force attack", calculating all the posibles values of "x" and "y"

    To speed up this task, I write a little python code:

    p = 31
    g = 15
    X = 23
    Y = 23

    for i in range(p):
    X2 = (g**i)%p
    Y2 = (g**i)%p

    if(X2 == X):
    print "X = %d, X2 = %d, i = %d" %(X, X2, i)
    if(Y2 == Y):
    print "Y = %d, Y2 = %d, i = %d" %(Y, Y2, i)


    And this is the output:

    X = 23, X2 = 23, i = 7
    Y = 23, Y2 = 23, i = 7
    X = 23, X2 = 23, i = 17
    Y = 23, Y2 = 23, i = 17
    X = 23, X2 = 23, i = 27
    Y = 23, Y2 = 23, i = 27



    In this case, the posible values of "x" and "y" are the same, next, I use these values to calculate "k" using the following python code:

    x = [7,17,27]
    y = [7,17,27]

    for i in x:
    for j in y:
    k = (g**(i*j))%p
    print "k = %d" %(k)


    And this is the output:

    k = 29
    k = 29
    k = 29
    k = 29
    k = 29
    k = 29
    k = 29
    k = 29
    k = 29


    We can see that all the values of "x" and "y", and even all the combinations can be used to broke the communication, and we can see that the secret key (value of k) is 29.

    References

    jueves, 30 de agosto de 2012

    [SC] 3. One time pad pseudo-randomness tests

    For this week, we had to test our one time pad keys generator.

    The goal is to ensure that our generator produces enough pseudorandom keys.

    To achieve that goal we need to satisfy the next requirements
    - The pseudorandom numbers should be enough uniformly distributed
    - The generation must be unpredictable and unreproducible.
    - The keys must be uncompressible.

    We must also ensure that our generator does not cause any kind of pattern.


    Tomada de http://www.random.org/analysis/

    In the image, we can see how the pseudorandom number generator of the function rand() from PHP have a high periodicy and the pattern thats causes a pattern, this is a very big vulnerability because, with the enough computing power, any pseudorandom generated key can be broken.

    If we fulfill the requirements we can ensure that our keys are unbreakable.

    Tests

    To tests my pseudorandom  keys, I perform the following tests:
    • Uniformity of pseudorandom integers
    • Uniformity of zeros and ones
    • Frequency Monobit Test
    • Frequency Block Test
    • Compression test

    Results

    1. Uniformity of pseudorandom integers.

    For this tests first I generate a new set of keys, the one-time-pad to test is conformed by a set of 100 keys with length 100 each one, that means that I produce 10000 pseudorandom numbers in a range from 0 to 126, then, I store them in a matrix (only for storage, nothing special). Then, I pass the matrix to a function that calculates the frequency of each number in the range 0 to 126.
    Then, with the frequencies calculated I proceed to plot them in a graph. This is the result


    We can see that the integers are semi uniform, sometimes there are some high levels of recurrence, sometimes are low levels of recurrence. This is only the first part, later we can tests if really the pseudorandom keys are really random.

    2. Uniformity of zeros and ones.

    After calculate the frequency of each integer, I proceed to tests the uniformity of zeros and ones, so, first I need to convert my key in a long binary string, for that I followed the rule:

    if(number >= 0 and number <=63) then number = 0
    if(number >=64 and number <=126) then number = 1

    With this method now my key matrix is a binary matrix, now I counted the amount of ones and zeros in each key and then I plot a graph with the results.



    The graph looks like the previous one, we can see that the amount of ones and zeros is also semi uniform, so, we can conclude that maybe the numbers that form each key are pseudorandom.

    For more confiability, I perform 2 officially tests for pseudorandom generators.

    3. Frequency Monobit.

    "The focus of this test is the proportion of zeroes and ones for the entire sequence. The purpose of this test is to determine whether the number of ones and zeros in a sequence are approximately the same as would be expected for a truly random sequence. The test assesses the closeness of the fraction of ones to 1/2, that is, the number of ones and zeros in a sequence should be about the same. 
    Note that if a generator fails this test then the likelihood of other tests failing is high."
    Tomado de  http://www.random.org/analysis/Analysis2005.pdf

    The parameter of this test is only n , the length of the key (list of ones and zeros, length 100), I pass all the matrix as parameter and I perform the tests 100 times (100 keys).

    This is the results of the tests:

    .......

    The pictures are croped, at the final, the tests shows the amount of passed tests and failed tests.
    We can conclude that our one time pad is suspicious to be a real pseudorandom keys because the 93% of the monobit tests was passed.


    4. Frequency Block.

    "The focus of this test is the proportion of ones within M-bit blocks. The purpose of this test is to determine whether the frequency of ones in an M-bit block is approximately M/2, as would be expected under the assumption of randomness. 
    Note that for block size M=1, this test degenerates to the Frequency (Monobit) test. 
    The parameters of the tests are the length of each block (M), the length of the bit string (n),  the sequence of bits as generated by the RNG or PRNG being tested (ε). ε ≥ n. 
    If the computed P-value is <0.01, then conclude that the sequence is non-random. Otherwise, conclude that the sequence is random. "

    Tomado de  http://www.random.org/analysis/Analysis2005.pdf

    Also, I pass all the matrix as parameter and I perform the tests 100 times (100 keys, each keys of lenght 100 with block length of  "key length / 10").

    The results:

     ......

    With the two tests performed we can conclude that, according to the results of the tests, our one time pad meet the requirements to be a real random keys because the 90% of the frequency block tests was passed.

    Summary:

    90% of the frequency block tests was passed.
    93% of the monobit tests was passed.

    5. Compression test.

    This is an extra tests that only to measures the compression ratio of the keys, so first we take the keys matrix and pass it as parameter to the function, then, reads each key and convert it to a string, next we apply the zlib.compress() to compress the key with a level of compression of 6 (default). Then I perform a summatory of the lenght of each keys (compressed and decompressed) and finally I compare the size of all the keys compressed and decompressed.
    The result was:


    If I try to compress the ones-zeros matrix, the result was:



    We have a little contradiction here, because, our randomness tests conclude that the keys was real random keys, but, the compression ratio is almost 50%



    5. Conclusion.



    I think that the keys in the tested one time pad are real random keys, because the graphs shows that the numbers are generated almost uniformly, also, we pass the official test of randomness.


    I think that the compression tests failed because the file is too small, maybe generating a long enough file the result will be better.


    6. Code.





    Referencias

    miércoles, 29 de agosto de 2012

    [SC] Extra. Chinese Remainder Theorem

    Congruence


    To begin, a congruence is a therm used to designate two different integers that have the same remainder when they are divided by a natural number.


    Mathematical Definition


    "Given a, b and m, with m > 0 that belongs to the set of integers, we say that a is congruent to b mod m if m divides
    exactly (a-b).
    a and b are congruent module m if and only if a and b have the same residue to be divided by m, individually.

    a ≡ b (mod m)
    m | (a - b)

    The expression is read "a is congruent to b module m" and m is considered the module of the congruence.

    P.E:
    • 27 ≡ 3 (mod 4), because (27 - 3) = 24, is divisible by 4 with remainder 0
    • 47 ≡ 7 (mod 8), because (47 - 4) = 44, is divisible by 8 with remainder 0
    • 1 ≡ -1 (mod 2), because (1 - (-1)) = 2, is divisible by 2 with remainder 0


    Properties


    The congruences have 3 properties:
    • Reflexive:
      a ≡ a (mod m)
    • Symmetric:
      IF a ≡ b (mod m) ⇒ b ≡ a (mod m)
    • Transitive:
      IF a ≡ b (mod m) ∧ b ≡ c (mod m) ⇒ a ≡ c (mod m)

    **NOTE: If you want to know more, please see the references at the final of the end of this post


    Chinese Remainder Theorem


    The Chinese Remainder Theorem is a method used in number theory to solve systems of congruences.

    A system with 2 or more lineal congruences don't have necessary a solution, even if each individual congruence have one. A system of lineal congruences is denoted by:

    b1x ≡ a1 (mod m1)
    b2x ≡ a2 (mod m2)
    bix ≡ ai (mod mi)

    But, all system with 2 or more lineal congruences which individualy accepts a unique solution, also accepts a simultaneous solution if the modules are comprimes with each other.

    The chinese mathematician Sun Tsu Suan-Ching pose the following problem around the 4th century b.C:

    "There are certain things whose number is unknown. Repeatedly divided by 3, the remainder is 2; by 5 the remainder is 3; and by 7 the remainder is 2. What will be the number?"

    Problems of this kind are all examples known as the Chinese Remainder Theorem. In mathematical words the problems can be solved finding n, given its remainders of division by several numbers m1, m2, ..., mk.

    Mathematical Definition


    Suppose that m1, m2, ..., mk are positive integers, relatively primes each other in pairs (mi, mk) = 1, if i ≠ k. And b1, b2, ..., bk are arbitrary integers. In the system of lineal congruences:


    x ≡ b1 (mod m1)
    x ≡ b2 (mod m2)
    ...

    x ≡ bk (mod mk)

    All the solutions of x are congruent module m, with m = m1 * m2 * ... * mk

    Proof


    M = m1 * m2 * ... * mk
    Mk = M/mk

    So, if all the modules are taken in pairs, and they are comprimes with each other, that means that gcd(Mk, mk) = 1, applying the rule gcd(a, m) = d, then, the congruency ax ≡ b (mod m) have a solution if, and only if d | b.

    Now, x = b1*M1*y1 + b2*M2*y2 + ... + bk*Mk*yk

    If we considerate each term of this summatory a module of mk.
    Given that Mi ≡ 0 (mod mk), if i ≠ k, we have that x ≡ bk*Mk*yk ≡ bk (mod mk).

    This means that x satisfies each one of the congruences of the system

    By the symetric property, if x and b are two solutions of the system, we have that x ≡ b (mod mk) for each k. And because each mk are relatively primes each other by pairs, we also have that x ≡ b (mod M).

    Example


    "Find the two minimal prime numbers that have remainders 2,3,2 when they are divided by 3,5 and 7 respectively.

    Solution

    The system can be modeled in a system of congruences:

    x ≡ 2 (mod 3)
    x ≡ 3 (mod 5)
    x ≡ 2 (mod 7)

    The solution starts:

    m = 3*5*7 = 105

    Then:

    M1 = m/3 = 105/3 = 35
    M2 = m/5 = 105/5 = 21
    M3 = m/7 = 105/7 = 15

    Next:

    y1 = M1 (mod 3) = 35 (mod 3) = 2
    y2 = M2 (mod 5) = 21 (mod 5) = 1
    y3 = M3 (mod 7) = 15 (mod 7) = 1

    Now, find x:

    x = b1*M1*y1 + b2*M2*y2 + b3*M3*y3
    x = 2*35*2 + 3*21*1 + 2*15*1
    x = 140 + 63 + 30
    x = 233

    Now we have 233 ≡ y mod(105)

    Applying the symmetry rule

    y ≡ 233 mod(105)
    233 mod(105) = 23

    The solution is 233 ≡ 23 mod(105), and 2 minimal integers could be 23 and 233, but, if we divide (233-23)/105, the result is 2, maybe there are another number where the result is one.

    1 = (x-23)/105 also 1 = 105/105

    Then

    105+23 = 128 and 1 = (128-23)/105

    The 2 minimal integers are 23 and 128.



    References

    jueves, 23 de agosto de 2012

    [SC] 2. One-time-pad Encryption

    In cryptography, the one-time pad (OTP) is a type of encryption which has been proven to be impossible to crack if used correctly. Each bit or character from the plaintext is encrypted by a modular addition with a bit or character from a secret random key (or pad) of the same length as the plaintext, resulting in a ciphertext. If the key is truly random, as large as or greater than the plaintext, never reused in whole or part, and kept secret, the ciphertext will be impossible to decrypt or break without knowing the key.
    The "pad" part of the name comes from early implementations where the key material was distributed as a pad of paper, so the top sheet could be easily torn off and destroyed after use. For easy concealment, the pad was sometimes reduced to such a small size that a powerful magnifying glass was required to use it. Photos show captured KGB pads that fit in the palm of one's hand,[7] or in a walnut shell.[8] To increase security, one-time pads were sometimes printed onto sheets of highly flammable nitrocellulose.

    http://en.wikipedia.org/wiki/One-time_pad


    For the first activity of this class, we have to write a python script implementing one time pad encryption.
    For my script I used the technique of modular addition to cipher and decipher. The steps of my script are:

    1. Generate the pads: Execute the file oneTimePad.py -G to generate the pads. The cipher pad name and the decipher pad name are requested before, also the number of keys to generate and the length of each key. Whole process happens silently and very fast.


      Basically, my pad generation function opens/creates the pad file, then, initialize a list of the same size that the lenght of a key, the list is filled with random integer numbers between 0 and 126 (the basic ascii code), that's means that my alphabet lenght is 127.
      When the list is full, I use the python join() function to convert it to a string and write it in the pad file. This is repeated until the specified amount of keys are created.
      Finally, I use the module shutil and import the function shutil.copy() to create a copy of the pad. One is the cipher pad and the other one is the decipher pad.


      Original message:




    2. Encrypt a message: Execute the file oneTimePad.py -C to cipher a message file. The name of the original message file, the name of the output file (encrypted message) and the name of the cipher pad file are requested.


      This function opens the input file (original message file), reads all the lines and merges them into a single and long line, then, converts the line in a list, now, each character is a element of the list. Opens the cipher pad file and read the first line to get the cipher key, also, converts the line into a list. Then, checks if the length of the message is less than or equal to the length of the key, if is lesser, punctuation marks are appended to the message list, if is equal nothing is done, if is greater, an error is raised and the script finish the execution. After the verification, the message is encypted character by character according the formula:

      (int(key[a]) + ord(message[a])) % alphabetLength

      Where a corresponds to the index of an element in the lists.
      The characters are converted first in their corresponding ascii codes, then, the corresponding value of the key is added, then the module of the alphabet length is applied. The result is appended in a output list. When all the characters were converted, the output list are converted in a string using the function join() and is written in the specified output file. Finally, the cipher pad file is opened and the first line is removed.


      Encrypted message:




    3. Decrypt a message: Execute the file oneTimePad.py -D to decrypt an encrypted message file. The name of the encrypted message file, the name of the output file (decrypted message) and the name of the decipher pad file are requested.


      This function opens the input file (encrypted message file), reads all the lines and merges them into a single and long line, then, converts the line in a list, now, each character is a element of the list. Opens the decipher pad file and read the first line, also, converts the line into a list. Then, checks if the length of the message is equal to the length of the key, if is lesser or greater an error is raised and the script finish the execution. After the verification, the message is decrypted character by character according the formula:

      (alphabetLength + int(message[a]) - int(key[a])) % alphabetLength

      Where a corresponds to the index of an element in the lists.
      The characters are converted first in their corresponding ascii codes, then, the alphabet length is added and the key value is substracted, then the module of the alphabet length is applied. The result is appended in a output list. When all the characters were converted, the output list are converted in a string using the function join() and is written in the specified output file. Finally, the decipher pad file is opened and the first line is removed.


      Decrypted message:



    We can see how punctuation marks was added at the final of the file. This was because the key length was greater than the length of the message.

    Code




    References