Steganography

Download

Stream Cipher: E0

Hi! for this week we need to choose a stream cipher to investigate and also put an example, so, I chose E0 which is the algorithm that is used to protect the confidentiality of communication protocol in wireless Bluetooth, developed by Bluetooth Special Interest Group (SIG) [1] including 1500 companies.

The pseudo-random generator consists with four LFSRs (Linear feedback shift register) combined by a function having 4 bits of internal memory which is updated by a nonlinear function. Bluetooth work on the principle of a protocol for master-slave type.

Vulnerability: E0 is vulnerable with the fast correlation attack that can recover the encrypthon key in 2^38 operations if we know the first 24 bits.

If we need to implement a security using E0 must have the following parameters.

• Key length: 128 bits, the key is always extended to a word of 128 bits by adding bits redundancy even when the actual number of bits is less key.
• Initialization 64 bits vector, corresponding to the logical address of the master (48 bits) and the data of the clock (22 bits).

Under the bluetooth protocol, data is transmitted in the form of frames more than 2745 bits, so, each frame is encrypted by modulo 2 bit by bit with the first output bit of the pseudo-random generatos, initialized with a secret key which is the same during the session and an initial value which is modified at each frame change.

Description

E0 diagram[6]

E0 uses a combination of four LFSRs[5], and having a 4 bits in memory, this is used at two different levels, it is applied once furing initialization to generate an initial state of 128 bits from the secret key and the first vector and the same mechanism is then used to produce the keystream from this initial state[4].

The four registers LFSRs are binary with this lengths L1 = 25, L2= 31, L3=33, L4 = 39, total = 128 bits.

If we denote xⁱ_t the output at time t with i-th LFSR, then we need to calculate the 3-bit integer (0 to 4) corresponding to the sum of the outputs of the four LFSRs.

We need a combiner function F, that is a 4-bit finite state machine, if we have c_t =(q_t , p_t , q_t-1, p_t-1) it's the registers of F and l(t) = x¹_t+ x²_t+ x³_t+ x⁴_t is integer addition.

The output of the combiner function is pt, so, p_t = F(x_t, c_t)
The state change by the following instruction:

where

S_t+1is the binary representation of the right number, 1 most significant bit and 0 least significant bit.

The output of the algorithm is:

So, we can say that the E0 algorithm made for each packet transmissions generates a new encryption that combine the four registers (complex RAND, device address, master clock, secret key), which has a 25, 31, 33, 39 bits, 128 in total, the secret key is used as an input to E0 to produce a bit stream pt that is added with modulo 2 to be encrypted.

Example
So, this is my example, I use for made the calculation, python in console mode.

We need 4 variables, with determinate bits:
RAND = 1101101000001010110100111  (25 bits)
Device Address = 1101111001010011010001010100011  (31 bits)
Master Clock =  111000001001110111101000111001001 (33 bits)
Secret Key =110010111000000010100110010100110001101 (39 bits)

I just use random numbers generates with the function getrandbits in python, then, we need to do LFRS, so this is one iteration, we need to select the position base on the polynomials and made the sum.
P1(x) = 1 + 0 + 0 + 1 + 1
P1(x) = 11

P2(x) = 1 + 0 + 0 + 0 + 1
P2(x) = 10

P3(x) = 1 + 0 + 0 + 1 + 1
P3(x) = 11

P4(x) =  1 + 1 + 1 + 0 + 1
P4(x) = 100

Then, we need to have  l_t
lt = 11 + 10 + 11 + 100
_lt = 1100

Then we need to calcule  F(x_t, c_t) if we have c_t =(q_t , p_t , q_t-1, p_t-1) as memory of previous iterations, base in [1] we have 2 states 2-bit that:

Suppose that we have this combination and a t = 35 seg:
q_t = 00
p_t = 01
q_t-1 = 11
p_t-1= 10

S_t+1= floor(pi(100011)+2*(00)+01/2)
S_t+1 = 11110

p_t = F(x_t, c_t)
p_t = 11110

Then we can calculate Z:
Z = (l(t) % 2) + Pt
Z = (1100 % 2) + 11110
Z = 11110

So, Z contains one bit stream encrypted, this change in the time and in the state.

Vulnerability
The generator by combining registers used in the algorithm e0 is vulnerable to several attacks, I can mention for example linear attack, algebraic and fast algebraic attacks and fast correlation attacks. Most of these attacks requires the knowledge of a large number of successive bits of the key, which is not possible in the practical context of the Bluetooth protocol since the initial state of the generator is changed every number of bits.

By cons, sophisticated correlation attacks, presented by Yi Lu, Wili Meier [2], take into the session the re-synchronization occurs after encrypting each frame, and also there are one most effective[3] that allows to recover the encryption key from the knowledge of the first 24 bits of 2223.8 frames in 238 operations, as a result, the algorithm used in Bluetooth e0 is clearly offers insufficient security.

Biography.
[1] Bluetooth special interest group link
[2] Cryptanalysis of Bluetooth Keystream Generator Two-Level E0, Yi Lu, link
[3] A Practical Arrak on Bluetooth Encryption, Vili Meier, link
[4] Criptografía Moderana, cifra de flujo, P. Caballero link
[5] Communication Systems Security, Appendix B.L. Chen, link
[6] Algebraic Attacks and Stream Ciphers, Mikko Kiviharju, link

Block Ciphers: RC5

Hi!, for this week we need to choose a block cipher to investigate and also put an example, so, I chose RC5, is a block cipher quick and easy, designed by Ronald Rivest in 1995 in the MIT's Laboratory of Computer Science, this encryption algorithm, works for hardware and software, use as a parameters the length of the word, the number of iterations and the length of the private key.

RC5 has the following characteristics:

• Is a symmetric cipher, both the encryption and decryption uses the same private key.
• It works in both, hardware and software because RC5 uses only elementary operations.
• Is adaptable to processors with different word lengths, for example, if we have a 64-bit processor, RC5 can use the entire length of the word.
• Has an iterative structure with a variable number of iterations.
• Has a cryptographic key variable length, this allows that the user can choose the desired level of security for your application and solves problems related to the export of cryptographic algorithms that use more than 40 bits keys.
• It is easy to implement.
• A request has limited memory, so it can be easily implement on devices with small memory.
• Provides a high safety
• Using data-dependent rotations, in which words are rotated cyclically.

One of the fundamental characteristics of RC5 is that uses three parameters, W, R, B, if two users exchange messages using RC5 for encryption must agree with that parameters.

• W: is the word length in bits. RC5 uses basically values such as 16, 32 and 64 in W, We need to know that RC5 cipher blocks of 2 words use the plaintext and the ciphertext uses 2W bits. so if we have a W = 32, the blocks of plaintext and ciphetext are of 64 bits.

• R: represents the number of iterations of the algorithm and varies from 0 to 255. the security level of the cipher depends from this parameter: the larger choose R, the better the security.

• B: is the length of the private key K. Allowed values of b are 0, 1, …, 255.

For convenience, we can use RC5-W/R/B to denote those parameters, for example, the algorithm RC5-32/16/10 uses 32-bits words, leaving 16 iterations of the algorithm and has a key of 80 bits (10 bytes). Not necessarily all the parameters must be specified. We can omitted the last parameter or can be omitted the last two. For example, with RC5-32, is indicated the RC5 algorithm that uses 32-bits words, without any reference to the number of iterations and the length of the key.

RC5 uses only the following three operations and their inverses:

• Sum of words module W/8, this operation is denoted by +, the inverse operation, subtraction, is denoted by -.

• Bitwise exclusive-OR, denoted XOR (The reverse is itself).

• Rotation to the left of words. The cyclical rotation of the word x of y bits to the left is denoted with 2^w y is considered the modulo w, so when w is a power of two, are need only x << y low order bits of y to determine the number of position to rotate. the reverse operation is to the right.

These operations are supported efficiently by many processors, the main feature of RC5 is the use of data-dependent rotations, rotations dependent on the plaintext and the key, also, the rotations are the only nonlinear operator in RC5.

The RC5 cipher contains the three following procedures:

• Key expansion algorithm
• Encryption algorithm
• Decryption algorithm

The plaintext input to RC5 consists of two w-bit words, contained in the registers A and B, also uses a "expanded key table" containing t = 2(r+1), obtained from the user's private key K.

The key expansion algorithm, use the secret key K, fills the key table S with t = 2(r+1) binary words, use also two "magic constants" P and Q. which are defined as a W for arbitrary.

Pw = ODD((e-2)2^w)
Qw = ODD((phi-1)2^w)

where e = 2.7182... , phi = 1.618... and ODD(x) is the odd integer closest to x.

For w = 16, 32, 64, have the following values in hexadecimal.

• Pw 16-bit = B7 E1
• Pw 32-bit = B7 E1 51 63
• Pw 64-bit = B7 E1 51 62 8A ED 2A 6B

• Qw 16-bit = 9E 37
• Qw 32-bit = 9E 37 79 B9
• Qw 64-bit = 9E 37 79 B9 7F 4A 7C 15

The key expansion algorithm is divided into two steps:

Conversion of the secret key from bytes to words. The B-byte secret key K [0 .. B-1] is copied into an array L [0 … c-1] of c words. each w-bit, so in this way, in L[0] is stored the first byte of the key and L[c-1] contains, if  necessary, of the null bits, added to make the key size equal to a certain number of words, namely 8*b must be a multiple of W. 

So, the size of the array L[] is c = [8*b/w]

Creation of the expanded key table, the array S is initialized by using an arithmetic progression modulo w/8 determined by magic constants, 

S[0] = Pw 

for i = 1 to 2r+1 do  

        S[i] = S[i-1]+Qw

Then the algorithm performs the actual expansion of the key processing arrays S and L in the following way:

X ,  Y = 0
i, j = 0
do 3*max(x, 2r+1) times:
X = S[i] = (S[i]+X+Y) << 3
Y = L[j] = (L[j]+X+Y) << (X+Y)
i = (i+1) mod (2r+1)
j = (j+1) mod c

So in S[0, …, 2*r + 1] contains the key will be scheduled. The expansion function key can be considered one way. It is not easy to determine K from S.

The encryption algorithm takes as input the plaintext stored in two registers A and B, each of w bits, the number r of iterations to be performed and the key, stored in S[0, …., 2*r + 1], returns the cipher text in the registers A and B, the algorithm in pseudocode:

A = A + S[0]
B = B + S[1]
for i = 1 to r do:
A = ((A XOR B) << B) + S[2i]
B = ((B XOR A) << A) + S[2i+1] 

The output is contained in the registers A and B.

We observe that RC5, at each iteration, updates both registers A and B. During each iteration of the DES, however, only half word is actually transformed, while the other half remains unchanged, Therefore an iteration on RC5 "is equivalent" in two iterations of the DES.

The decryption routine is easily derived from the encryption routine: just do the reverse in reverse order:

for i = r downto 1 do:
B = ((B-2[2*i+1] >> A) XOR A
A = ((A - S[2i]) >> B) XOR B
      B = B - S[1]
      A = A - S[0]

The output is stored in the registers A and B containing the plaintext.

The RC5 algorithm is extremely simple. Its cryptographic strength depends heavily on the use of data-dependent rotations. Sice they depend on the input data, do not allow to collect statistics and avoid attacks of differential cryptanalysis and linear cryptanalysis.

I tried to understand the vulnerabilities of the RC5, I saw that if we have two similar plaintext blocks can give us results very similar, so I put the example about that:

This is first iteration and we already have the table expansion.

A = A XOR B 

A = A << B 

A = A + S[i] 

B = B XOR A 

B = B << A 

B = B + S[i+1]

A = 11111101100001001101111001100011
B = 10110001100110011010111100110001
   

Now, we can made the first 3 steps.

A = A XOR B

A =
      11111101100001001101111001100011 XOR
      10110001100110011010111100110001
      ---------------------------------------------------------
      11001100000111010111000101010010


A = 11001100000111010111000101010010

A = 11111101100001001101111001100011 << 10110001100110011010111100110001

A = 11100010101001011001100000111010

A = A + S[i]

A = 
   11100010101001011001100000111010 
+ 01110001100111101110010011011001
    --------------------------------------------------------
    01110001000001011011001101100001

A = 1110001000001011011001101100001

Then, imagine that we have a A and B just only one letter different.

A = 11111101100001001101111001100011
B =  00110001100110011010111100110001

Now, we can made the next 3 steps.

A = A XOR B

A = 11111101100001001101111001100011  XOR
       00110001100110011010111100110001
    -----------------------------------------------------------
       11001100000111010111000101010010

A = A << B

A = 11001100000111010111000101010010 << 00110001100110011010111100110001

A = 11100010101001011001100000111010

A = A + S[i]

A = 11100010101001011001100000111010
     + 01110001100111101110010011011001
     ----------------------------------------------------------
       001110001000001101011001101100001

A = 1110001000001101011001101100001


Now, compare A.

A_1 = 1110001000001011011001101100001
A_2 = 1110001000001101011001101100001

You can see that we have two plaintext blocks very similar, if we have the ciphertext very similar, we have a problem because an attacker can see that ciphertext blocks and check similarities to have things for the plain text.

So it is important to know that we have issues that involves vulnerabilities but we can improve put, as I explain in the algorithm,  put a lager R that represents the number of iterations of the algorithm and varies from 0 to 255. the security level of the cipher depends from this parameter: the larger choose R, the better the security.

Bibliography.
* The RC5 Encryption Algorithm MIT, Ronald Rivest link

Game Cards

1. Self-enforcing
2. guarantee
3. ideal
4. Compressible
5. disinterested
6. ambiguos
7. passive
8. interruption
9. One-time-pad
10. Challenge

RSA-based digital signature

For this homework I need to implement a HTTP public-key repository for key exchange that employs RSA-Based digital signatures, so for make this assignment I used PHP and a little database in mysql also a little script in Python.

First of all, this is my code:

This is the PHP+MySQL code

This is the Python script.

This is the MySQL database.
You can access to the application robertomtz.comeze.com/cripto.php

This is useful for example, I am not sure that cecy is the same person that I am chatting on facebook, so Cecy is on my database with a public key and I sent a challenge to Cecy and she download a script that run in local, put her keys and compute a r, she sent me the r and I verify in my web that it was Cecy.

This is an example that I made with Cecy 

If I put an incorrect Response:

:)

RSA authentication in Python

Hi!, for this week we need to implement an RSA authentication in Python for a client-server system with sockets, so I made 3 scripts, one script is the Server that has the following steps:

• We need a listener wait for a client
• Accept a socket
• We need to load e and n from a file
• Send a random number and send it to client
• Compute a y = r^e%n
• Check if we have the same value
• We have a login

The other script is the Client that has the following steps:

• Looking for a socket
• We need to load d and n from a file
• Compute y = f(x) and then r = y^d%n
• Wait for login

Server

Client

Generator keys
Also I made a generator of keys, following the slides from the course.

This is how works my code, for example, if we need a new user:

User.dat = User d n

Claves-Server.txt = User e n 

But, if we try to login with a different user.

Report 1: Hack manually

Hack manually (pencil and paper) a veryshort keyed Diffie-Hellman of your choice

I verify with Cecy if we have the same K.

Adecuate randomness

On my last homework, I made the one time pad, if the key are truly random, one time patd is unbreakable and if someones stole the key that's not fault in the algorithm, it is the fault in the store the key.

Cryptography secure adecuate randomness means that is officially random, don't have any patterns that anybody could use for brake the algorithm, if you are making one time pad, you have a pseudorandom generator that has patterns.

If we have patterns or periodicity we have a vulnerability in the one time pad and somebody can synchronize for have my keys that I made with the key generator, and people could get the sequence of the key.

In this report, I'm going to explain and made different test for randomness, and demonstrate if I have a secure or insecure system, at the end I'm going to make a conclusion about it.

First at all, I'm going to make a statistical test for randomness, as you need to know, randomness is a probabilistic property, so we can use different test for make sure that my data have a true random data, I made two different test, a frequency test and a Runs test, I implemented in python, this is my code that generate key using random.choice and select a 15 symbols in ascii then I translate those into integer for made an XOR in the one time pad implementation.



In the frecuency test this are the steps:

• We need to compute the test statistic: Sobs = abs(s)/sqrt(n) where sn are sum of all the zeros in -1.
• Then, we need to compute P-value = erfc(Sobs/sqrt(2)), where erfc is the complementary error function.
• At the end, we need to know if P-value is small (< 0.01), accept the sequence as random

In runs test this are the steps:

• We need to compute the pre-test proportion pi of ones in the input sequence:
• sum_pi = SUM(number zeros-ones)/n
• Compute the test statistic Vobs = SUM(r(k))+1
• When r(k)=0 if the value of array of number zeros-ones it's the same that the next one, and r(k) = 1 otherwise.
• Compute P-value = erfc( abs(Vobs-2n*sum_pi*(1-sum_pi))/2*sqrt(2n)*sum_pi*1-sum_pi)
• If >= 0.01, accept the sequence as random

In based on Secure Telecomunication System slides[1], the recommendation for made the test is for both, Runs and frequency, has a input size minimum 100, so this are the result.

So  in both test, we don't have a good random sequence, to conclude, my implementation is insecure because it not truly random and somebody can have patterns or periodicity and synchronize and have my keys.

Then, I change the random import from python to randint from numpy, I run the same test and I have the same result, sequence are not accept as random by frequency test, as well as runs test.

Then,  I made a comparison between have a compress file with 100000 random numbers and make zip, for pass this test, they cannot be smaller because, as you know, the compress algorithm look for repeat sequence and replace long sequences with short sequences, we can look at the weight compress by kb.

This are the result:

So in the test, we don't have a good random sequence again, because we can compress the file about 46 %, we can conclude, that my implementation is insecure because it not truly random because we can compress the file.

So, for make a conclusion, we can see that in the three test, we don't have a good response and we have a one time-pad very insecure, so we need to develop with a truly random generator key for have a good implementation, only change the key generator, because in the algorithm, we don't have problem, we have problem at making the keys, we need to know that most of the computation random generators are called pseudo-random, because they use a deterministic algorithm, in most of the case is OK for make programs but, in this case, make the one time pad insecure, so, I investigate and we can use a random generate by OS like os.urandom() in python, but never we can have a truly random generator by computer, only if we can have something mechanical like random.org or maybe in the future.

Bibliography
[1] Slides of Secure Telecommunication System here.

ONE-TIME PAD -- Python

This is my intro homework implementing ONE-TIME PAD, I made two different script, one for make the keys and save it into file, and then a simulation script, those are the codes.

This code generate keys, using choice and library string

This code made a simulation that take the keys and erase from the file, that's exactly how works one-time pad.
This is the sample out of how works my code.


Robertomtz-2:Desktop roberto$ python genera_key.py
<open file './Roberto/key_1.txt', mode 'w' at 0x10e1e4ae0>
<open file './Ramon/key_2.txt', mode 'w' at 0x10e1e4b70>


463763421315310488663110378560176982
396445231729019104983631110994544205
417134473902073172990551648684034887
354461120138371425565563466647161416
406749964060333827409156118218752342


<closed file './Roberto/key_1.txt', mode 'w' at 0x10e1e4ae0>
<closed file './Ramon/key_2.txt', mode 'w' at 0x10e1e4b70>


Robertomtz-2:Desktop roberto$ python OTP_sim.py
Menu
1. Enviar a Roberto
2. Enviar a Ramon

>> 1
Escribe el mensaje a enviar a Roberto

>> Hola amigo
Llave usada por Ramon = 463763421315310488663110378560176982
Mensaje codificado 463763421314970161502469700003374137
Recibido por Roberto
Ahora Roberto lo va a decodificar
Llave usada por Roberto = 463763421315310488663110378560176982
Mensaje decodificado Hola amigo
Menu
1. Enviar a Roberto
2. Enviar a Ramon

>> 2
Escribe el mensaje a enviar a Ramon

>> Como estas
Llave usada por Roberto = 396445231729019104983631110994544205
Mensaje codificado 396445231728711576779657101873915710
Recibido por Ramon
Ahora Ramon lo va a decodificar
Llave usada por Ramon = 396445231729019104983631110994544205
Mensaje decodificado Como estas
Menu
1. Enviar a Roberto
2. Enviar a Ramon

>> 1
Escribe el mensaje a enviar a Roberto

>> bien y tu
Llave usada por Ramon = 417134473902073172990551648684034887
Mensaje codificado 417134473902072616769792045078101810
Recibido por Roberto
Ahora Roberto lo va a decodificar
Llave usada por Roberto = 417134473902073172990551648684034887
Mensaje decodificado bien y tu
Menu
1. Enviar a Roberto
2. Enviar a Ramon

>> 2
Escribe el mensaje a enviar a Ramon

>> bien tambien
Llave usada por Roberto = 354461120138371425565563466647161416
Mensaje codificado 354461109587947668995530738586365734
Recibido por Ramon
Ahora Ramon lo va a decodificar
Llave usada por Ramon = 354461120138371425565563466647161416
Mensaje decodificado bien tambien
Menu
1. Enviar a Roberto
2. Enviar a Ramon

>> 1
Escribe el mensaje a enviar a Roberto

>> me da gusto        
Llave usada por Ramon = 406749964060333827409156118218752342
Mensaje codificado 406749964015467211724918636957414713
Recibido por Roberto
Ahora Roberto lo va a decodificar
Llave usada por Roberto = 406749964060333827409156118218752342
Mensaje decodificado me da gusto
Menu
1. Enviar a Roberto
2. Enviar a Ramon

>> 2
Ya no existen llaves

Cryptography exercises

(`)t|<s(|x<^<(|"<_xQ=__$<)^<_^|l<|<^)s<:t_x^)tiQ=__%:<t_x<(+<s(+xs+:<:t_^:+:Q:t+|^:(})l<=`<s(+]|%=<_t|<:l+$<_x^Q^:_t<|<:l__(<_x:<l_t+^<:t_x^)&Q^:_i<]|l(`:<:+x<:t|_}<t_x^|-QQ<t`)<-)<_%ll+&<_x^<(+<_:`)x<t`)Q^__t^:<t`)<-)<_%ll+&<_x^<(+<_:`)x<t`)QQ)`t<x)`:_<+(<^x_<&+ll%_<)-<)`t<:^t__^Q)`t<x)`:_<+(<^x_<&+ll%_<)-<)`t<QQ)`t<x)`:_<+^<x|:<|<"t)}lQ^x_t_:<|%}|]:<:)&_^x+(s<x|==_(+(sQ|(l<+^:<`:`|%%]<?`+^_<%)`lQ)`t<&`&<:x_:<:)<x)`:_<=t)`lQ()^x+(s<_{_t<:%)}:<x_t<l)}(Q|(l<|<&_::<+:<()^<|%%)}_lQ