Clase Criptografía - Firma Digital

Code Steganography

This is my code I used to hide the message in the images. The algorithm I made it thanks to my classmate Alejandro Avendaño thats why is very similar, well here is the code



And this was my first attempt but but I got stuck :C in this attempt I was manipulating binary

Steganography

sbs!

Py (cipher)

What is a Stream cipher?

A stream cipher is a symmetric key cipher where plaintext digits are combined with a sequence of bits used as a key which is called keystream. In a stream cipher each character or number of the plain text is encrypted one at a time with the corresponding digit of the keystream, and the result will be a digit of the cyphertext stream. Encryption is accomplished by combining the keystream with the plaintext, usually with the bitwise XOR operation.

This keystream is typically generated serially from a random seed value using digital shift registers. The seed value serves as the cryptographic key for decrypting the ciphertext stream.

Stream ciphers can be designed to be exceptionally fast, much faster than any block cipher, that's because stream ciphers typically operate on smaller units of plaintext, usually bits.

Py cipher

Py (written in the Cyrillic alphabet, thus pronounced Roo). is a stream cipher submitted to eSTREAM (a project to "identify new stream ciphers suitable for widespread adoption") by Eli Biham and Jennifer Seberry. It is one of the fastest eSTREAM candidates at around 2.6 cycles per byte on some platforms.

Py is a stream cipher designed for very fast and secure encryption of extremely long streams. It is use with keys of up to 256 bits, and initial values ( up to 128 bits), but it also allows longer keys of up to 256 bytes, and intitial values sizes up to 64 bytes; keys and initial values should be in multiples of a byte, and at least one byte in length. Talking about speed, Py spends only about 2.85 cycles/byte on stream generation in its efficient implementation.

A second variant of Py, called Py6, is used for shorter streams. This variant has smaller rolling arrays, thus its key setup and IV setup are much faster than of Py

Here a comparison between Py, Py6 and RC4 ciphers in 4 different processors

The allowed stream size is 2⁶⁴ bytes in each stream (or 2⁴⁰ in the smaller version Py6). The most important thing of Py is called rolling arrays, these arrays are rotated and updated over time in a way that allows both the data to be updated very quickly and a very efficient implementation.

Py cipher uses rolling arrays which are vectors whose units are cyclically rotated every rotation step by one unit. A useful property of rolling arrays is that if you access the same entry in two consecutive steps, the contents of this entry are expected to be different. An example of a rolling array algorithm is: for some entry k, the swap exchanges entry 0 and entry k, and then the rotation is performed.

The cipher Py maintains two rolling arrays P and Y and one word variable s. P is an array of 256 bytes that contains a permutation of all the values 0, . . . , 255, and Y is an array of 260 32-bit words, indexed −3, . . . , 256. In each step of the cipher the two arrays are rotated, and two output words (a total of eight bytes) are computed. The word s is updated by mixing two words of Y into it, where the two words are indirectly selected by indices from P, and then a variable rotation is performed, which rotates s by a number of bits which is taken from another entry of P.

The update of the rolling array (i.e., entry Y [−3]), and the computation of the two output words are very similar: take a rotated value of s, XOR it with a value of Y (with a direct access to a fixed entry of Y ), and add a value from Y which is accessed indirectly through a fixed entry of P

This cipher uses a key schedule which initializes the array Y from the key. In order to have a fast non-linear mixing, it uses an 8x8-bit S box. The key setup starts by initializing a 32-bit word s to depend on the key size and the first and last bytes of the key, by setting one of its bytes to be the value of the internal permutation applied on the key size (minus one, to ensure it is in the range 0–255). The next byte applies the permutation in the same way on the IV, but this time it is XORed with the previous computed byte before the application of the permutation.

Here is in pseudocode an algorithm of Py cipher and more especific, how the rolling arrays can be implemented:

The above pseudocode I found it in Py (Roo, åø): A Fast and Secure Stream Cipher using Rolling Arrays text written by Eli Biham and Jennifer Seberry, below in references is the link to ecrypt site where I found this text.

Attacks and vulnerabilities

the best cryptanalytic attack on Py, which was made by Hongjun Wu and Bart Preneel, can under some circumstances recover the key given partial keystreams for 224 chosen initial values.

Given only known plaintext, there is a distinguishing attack on the keystream made by Paul Crowley, which requires around 272 bytes of output and comparable time.

Py's security bounds limit any attacker to a total of 264 bytes of output across all keystreams everywhere

References

• Stream_cipher
• eSTREAM
• rsa
• ecrypt
• wikipedia

MacGuffin cipher

In the last entry I wrote a little about block ciphers, now in this entry I'm going to wrote about the MacGuffin block cipher.

Origin

MacGuffin is one of the earsliest a block cipher design created in December 1994 by Bruce Schneier and Matt Blaze at a Fast Software Encryption workshop. The name of this cipher comes from the acronym of the class of ciphers to which it belongs, that is the Generalized Unbalanced Feistel Networks, GUFN's, hence MacGuffin.

Purpose of MacGuffin Cipher

It was intended as a catalyst for analysis of a new cipher structure, known as Generalized Unbalanced Feistel Networks (GUFNs). This unbalanced Feistel network has 32 rounds and it is similar in structure to the NSA's Skipjack algorithm.

Another purpose of this algorithm was to explore the security properties of unbalanced Feistel networks.

Description

MacGuffin is also similar to Data Encryption Standard (DES), it takes a block of 64 bits of plain text to encrypt, takes a secret key that is 128 bits long, performs its transformation based on the key, and produces as output 64 bits of text that should be incomprehensible to anyone who doesn't know the secret key.

Their main change compared with DES, is that MacGuffin was spliting the DES 64 bits data block into two unequal halves in the Feistel network, 48 bits of the 64-bit data block are fed through the round function, whose output is XORed with the other 16 bits of the data block.

In other words this algorithm split the text into two parts with one part repeatdly modified according to a keyed function of the other part. In each round of the cipher it modifies only 16 bits according to a function of the other 48 bits.

Schneier and Blaze recommended using 32 rounds, and specified MacGuffin with a 128-bit key.

We were talking abour Feistel cipher and Feistel network, but what is that? 

Well a Feistel cipher is a symmetric structure used in the construction of block ciphers. A Feistel network is an iterated cipher with an internal function called a round function

Principles

Each round operates only with 16 bits and we use 32 rounds. Because there are twice as many rounds, however, there are also a total of twice as many key bits XORed with the control blocks.

We adapt our S-boxes directly from those of DES. The eight DES S-boxes each produce four bits of output. Since we require only two bits from each (that give us a total of 16 bits), we use only the "outer" two output bits from each S-box.

In each round, each control block bit is XORed with one derived key bit and provides one input to exactly one S-box. The control bits are mapped 1 : 1 to S-box inputs according to a fixed permutation. This permutation was designed so that each S-box receives two of its six inputs from each of the three registers in the control block.

Algorithm

Encryption

This diagram in the right side shows one round of MacGuffin block cipher.

• The 64-bit data block is divided in four 16-bit words (each word is represented in the diagram by one line). 
• The rightmost three words are XORed with subkey bits derived from the secret key. 
• They are then fed through eight S-boxes, each of which takes six bits of input and produces two bits of output. 
• The output (a total of 16 bits) is then recombined and XORed with the leftmost word of the data block. 
• The new leftmost block is then rotated into the rightmost position of the resulting data block. 
• The algorithm then continues with more rounds until the 32 round.

Decryption

MacGuffin's key schedule is a modified version of the encryption algorithm itself.

To decrypt am encrypted message is very easy because MacGuffin is a Feistel network; simply run the encryption algorithm in reverse.

Vulnerabilities

Vincent Rijmen (of AES/Rijndael fame) and Bart Preneel performed a cryptanalysis of MacGuffin and showed that it was quite vulnerable to differential cryptanalysis and linear cryptanalysis, but also showed it could be significantly strengthened by making only a few minor changes in its use of S-boxes. This happened during the same workshop MacGuffin was presented.

The algorithm was experimental, intended to explore the security properties of unbalanced Feistel networks. The cryptanalysis proceeded very quickly, so quickly that the cipher was broken using differential cryptanalysis at the same workshop by Vincent Rijmen and Bart Preneel. They also tried attacking MacGuffin with different S-boxes, taken directly from DES. This version was slightly stronger.

Example

Here are some pseudocodes about the key setup, encryption and decryption of this block cipher, I found it in this pdf of Bruce Schneier paper-macguffin.pdf

Encryption

Decryption

Keys Setup

Sources

• Feistel_cipher
• everything2
• MacGuffin_(cipher)
• paper-macguffin.pdf
• MacGuffin_(cipher)

Block cipher

Conventional cryptosystems are widely used throughout the world today, and new systems are published from time to time. 

There are two kinds of one-key ciphers: 

• stream ciphers
• block ciphers 

In stream ciphers a long sequence of bits is generated from a short string of key bits, and is then added bitwise module 2 to the plaintext to produce the ciphertext. In block ciphers the plaintext is divided into blocks of a fixed length, which are then encrypted into blocks of ciphertexts using the same key.

The block cipher is one of the more popular methods for hiding information. Is a type of symmetric-key encryption algorithm in which an algorithm and key are applied to a block of data (for example, 64 contiguous bits) at once as a group rather than to one bit at a time.

Decryption is performed by applying the reverse transformation to the ciphertext block using the same secret key

Using this encryption we assure that identical blocks of text do not get encrypted the same way in a message.

The first thing that a block cipher must do is break the original text or plaintext into blocks of equal size. A block is a group of characters, like 'iamablock'. The most common block size is 8 characters, or 64 bits. If the total number of characters in the plaintext is not divisible by the block size, then extra characters are generally added on to the end of the plaintext until a complete last block can be formed in other words extra characters are appended in order to have an eight-character block. Here is an example using a quote by former U.S. President Franklin Delano Roosevelt:

plaintext:                   The only thing we have to fear is fear itself

modified plaintext:   Theonlythingwehavetofearisfearitself

plaintext in blocks:   Theonlyt hingweha vetofear isfearit selfXend

This method of adding additional data or characters in order to make a complete block is called padding. 

Now that we have the information in chunks of 8 characters or in blocks, each block is transformed into another equally sized block. For example, we  have a block size of eight characters, each block would be transformed into a different, eight-character ciphertext block using any other cryptographic technique to transform each block. For this example we are going to use a simple transposition cipher to encrypt each block

plaintext:                  The only thing we have to fear is fear itself
plaintext blocks:      Theonlyt hingweha vetofear isfearit selfXend
ciphertext blocks:    tylnoehT ahewgnih raefotev tiraefsi dneXfles

ciphertext:                tylnoehTahewgnihraefotevtiraefsidneXfles

The cipher that we use to encrypt the plain text in blocks es very simple, we just reverse each block, this means that the last character becomes the first, the second becomes the second to last and so on. For more security, we can send the message in blocks of a different size than the original used. For example the ciphertext can be sent in this form:

ciphertext: tylno ehTah ewgni hraef otevt iraef sidne Xfles

This technique may no represent any difficult for decoding this text. Simply by reversing all the text and eliminating the white spaces. This is just for making an example and understand better about block cipher.

Eliminating white spaces and reversing the text, it would be like this:

ciphertext: selfXendisfearitvetofearhingwehaTheonlyt

We just need to figuring out the eight-character block size, and reversing the order of the blocks.

Sources

• searchsecurity.techtarget
• library.thinkquest.org
• daimi.au.dk

Algoritmo RSA

For this week, the homework was to implement the RSA Algorithm, for doing this I have to create private and public keys and create sockets for the server and client. I follow the next steps:

• I choose p and q, these numbers have to be primes and random
• Then I get n by multiplying p*q
• After this I calculate phi, using this formula (p-1)(q-1)
• Next I implement the Extended Euclidean Algorithm to get d (for private key)
• Then I choose e and check that this number is greater than 1 but less than phi
• Then create the public.txt and private.txt
• Create the server.py and client.py following this steps:

Well, with this assignment it was difficult to me to understand the Extended Euclidean Algorithm and I lost a lot of time with that and I could only get the parameters for the public and private keys, and because of that I couldn't do the sockets.

I thank my classmate Obed Guevara for helping to understand the part of the sockets, and during this week I would get this RSA algorithm complete.

Well, here is the code for getting the parameters.

Sources

• Extended Euclidean Algorithm - Wolfram &  trans4mind
• Wikipedia
• rsa

Diffie-Hellman protocol

Some theory....

This protocol is a key agreement protocol, and also is called exponential key agreement. This protocol was developed by Diffie-Hellman in 1976 and was published in the ground-breaking paper "New Directions in Cryptography.

This protocol allows two users to exchange a secret key over an insecure medium without any prior secrets. For this protocol it's necessary to use two system parameters p and g, this parameters are both public and may be used by all the users in a system. Parameter p is any prime number and parameter g (usually known as a generator) is an any integer that has to be less than p-1 inclusive. Also there is a property that must be satisfied: for every number n between 1 and p-1 inclusive, there is a power k of g such that n = g^k mod p.

Let's see an example to understand better.

Suppose Alice and Bob want to agree on a shared secret key using the Diffie-Hellman protocol. They proceed as follows: 

• First of all they have to agree in a prime number p and in a integer g less than p-1 inclusive. 
• Then, Alice generates a random private value x and Bob generates a random private value y. Both x and y are any integer and this values are private, this means that nobody has to know them. 
• After this, Alice sends a public value X that is g^x mod p and also Bob has to send a public value Y that is g^y mod p. They exchange this public values. 
• Finally, Alice calculates K = (Y^x)% p, and Bob computes K = (X^y)% p. If those are equal, Alice and Bob now have a shared secret key k.

Here is an image that explains what I said above:

We can think that this protocol is vulnerable because p and g are public, but the truth is that even if the attacker knew these values and also captures the messages, he won't be able to know the secret key. This protocol can be broken if we use small values for p and g but current implementations of this protocol use very large numbers that prevents an attack

Exercise for this week

In this assignment we have to hack the Diffie-Hellman protocol. Two classmates (Pedro Miguel and Alejandro Avendaño) were Alice and Bob and I act as an eavesdropper (let's call me Eve); they encrypt their "message" using the following data:

• P = 13
• g = 9
• Y = 1
• X= 3

The formulas that I can use to hack this protocol are:

• X = (g^x)%p
• Y = (g^y)%p
• K = (Y^x)%p
• K = (X^y)%p

The goal was to recover x and y and K

Well to hack this protocol I used the brute force attack strategy and also some reverse engineering.

• First, I calculate X and Y.

n = (9²) % 13

n = 81 % 13

n = 3 = X

n = (9³) % 13

n = 729 % 13

n = 1 = Y

With this two calculates I thought that I have hacked my classmates because:

(Y^x)%p = (X^y)%p

(1²)%13 = (3³)%13

1 = 1

But I get x wrong, so I did more calculates

n = (9⁴) % 13

n = 6561 % 13

n = 9

n = (9⁵) % 13

n = 59049 % 13

n = 3 = X

I found that also x = 5 gets the same K, and know it was correct!

(Y^x)%p = (X^y)%p

(1⁵)%13 = (3³)%13

1 = 1

Sources

• rsa.com
• mathworld.wolfram
• javiercampos

Statistical Tests. Runs Test

According to Wikipedia, a numeric sequence is said to be statistically random when it contains no recognizable patterns or regularities; pseudorandomness is sufficient for many uses, such as statistics, hence the namestatistical randomness.

The main idea of a random sequence is that each number has equal chance of occurring.

It exists some tests for proving that a sequence of numbers are random. The first tests were published by M.G Kendall and Bernard Babington Smith, those tests was built on statisticals tools like Pearson's che-squared test.

The National Institute of Standards and Technology (NIST) have made some tests for random and pseudo-randomnumber generators that may be used for many purposes including cryptographic, modelingand simulation applications. There is a total of 16 tests; 14 of 16 of these tests are designed for generators that produce a sequence of bits, being therefore focused on cryptographic applications.

The main distributions used in these tests are the Standard Normal distribution and the Chi-square distribution. The first one is used to compare the test statistic obtained for the random number generator with the expected value of the statistic under the assumption of randomness. The Chi-square distribution is used to compare the goodness-of-fit of the observed frequencies of a sample measure to the corresponding expected frequencies of the hypothesis distribution

Well, for this week I choose the Runs Tests from these 14 tests, and here is some information about this test and also a program in python that takes the keys that I used to cypher the text in the One Time Pad programa of last week. The purpose of this test is to prove that Python's random it is actually random and no pseudorandom numbers.

What is the Runs Test?

Well, the main purpose of this test is to determine if the number of runs of ones and zeros are a random sequence. In this context a run is an uninterrupted sequence of identical bits. A run of length k consists of exactly k identical bits bounded before and after with a bit of the opposite value.

In general, the parameters of this test are:

• n = the length of the input sequence in bits.
• ε = the sequence of bits that is going to be tested. ε = ε1ε2… εn
• The total number of sequences.
• The total number of the first element (in cryptography is 1 or 0)
• The total number of the second elelement (in cryptography is 1 or 0)

Having all this parameters now is turn to know which operations are going to be used:

• Mean:

• Variance:

• Probability

Now, below is the code that asks for a message to the user and this message is converted into binary and after that the keys are generated

And finally here is the code of the Runs Test, that takes as input the file that has the keys to encrypt the message.


At the end of the program the probability is compared with 1.96 because this number is from a standard normal table; and at the 5 % significance level, a test statistic with an absolute value greater than 1.96 indicates non-randomness.



Here is the program running

Sources

• Frecuency-Monobit-Test
• Statistical Randomness (Wikipedia)
• itl.nist
• Webspace
• Critical Values
• Runs Test (Wikipedia)

One time pad

Well this week I have to make a program using the one time pad method.

What I have to do?

• First, I have to create x number of keys, this keys have to be binary numbers
• Second, the program asks the user for a message to encrypt. This program writes the key that use and the cypher text in a file
• Third, the program using another function opens the file with the cypher text and the key and decrypt the cypher text.

For this program I use the xor function to encrypt the message, so the program takes each value of the binary text and each value of the key and applies them the xor function

An example could be if the binary message is 0100101 and the key 0001101, the cypher text would be:

message: 0100101

key:        0001101

cypher:   0101000

Here is my program:

(Note: due to time I couldn't make the function to decrypt the message, I just only implement the function to encrypt the message)

Here are some images of the program running:

• In this image we can see each character of the message being encrypted

• This is the file where I have the keys:

• Here is the file where I have the key and the cypher text

Cyphert Text

Here is my cypher text, good luck! ;)

?-g\t=;2m(,\ncv.W!Sl3g