State University of New York at Albany Write a Program to Find a Pair Questions

Question 1::::For each of the above two hash functions, show/analyze on paper whether the function follows the three properties: one-way, weak collision resistance, and strong collision resistance.

If the function does not follow any of these three properties, write a program to showcase it. In other words, for this you will do the following:

One-way: Let’s say if the function doesn’t follow one-way property, then write a program to calculate x, given its hash value h(x). In this case, you will demo that your code can calculate at least one such x. Weak-collision Resistance: If the function lacks weak-collision resistance, then write a program to find a y, given x, such that h(x) = h(y). In this case, you will demo that your code can find at least one such y. Strong-collision Resistance: If the function doesn’t satisfy strong-collision resistance, then write a program to find a pair (x, y), such that h(x) = h(y). In this case, you will demo that your code can find at least one such pair (x, y).

Question 2::::

a)  Design and implement a Pseudo Random Number Generator (PRNG) using AES in OFB mode. You can use any publicly available code or a library function for AES. Demonstrate that your implemented PRNG can output at least 10 random numbers (each with 128 bits). (Refer to Slide 24 of Lecture 10)

(b)  For these 10 numbers, calculate the Fraction of One Bits, and the Fraction of Bits that Match with the Preceding Block. (Refer to Slide 25 of Lecture 10)

ICSI-526/426 Cryptography
Pseudorandom Number Generation
and Stream Ciphers
Pradeep Atrey
SUNY, Albany
• Which of these sequences is more
random?
– 1110011010100100101010111100110001011
01001010
– 1111111000000111100001011111111000000
000001111
Random Numbers
• A number of network security algorithms
and protocols based on cryptography
make use of random binary numbers:
– Including generation of a bit stream for
symmetric stream encryption
Randomness
There are two distinct
requirements for a
sequence of random
numbers:
Unpredictability
Randomness
• The generation of a sequence of allegedly
random numbers being random in some
well-defined statistical sense has been a
concern.
Two criteria are used to validate that a sequence
of numbers is random:
Uniform distribution
• The frequency of occurrence of ones and zeros should be
approximately equal
Independence
• No one subsequence in the sequence can be inferred from the
others
Unpredictability
• The requirement is not just that the sequence of
numbers be statistically random, but that the
successive members of the sequence are
unpredictable
• With “true” random sequences each number is
statistically independent of other numbers in the
sequence and therefore unpredictable
– True random numbers have their limitations, such as
inefficiency, so it is more common to implement
algorithms that generate sequences of numbers that
appear to be random
– Care must be taken that an opponent not be able to
predict future elements of the sequence on the basis
of earlier elements
Pseudorandom Numbers
• Cryptographic applications typically make use
of algorithmic techniques for random
number generation
• These algorithms are deterministic and
therefore produce sequences of numbers
that are not statistically random
• If the algorithm is good, the resulting
sequences will pass many tests of
randomness and are referred to as
pseudorandom numbers
True Random Number Generator
(TRNG)
• Takes as input a source that is effectively random
• The source is referred to as an entropy source and is
drawn from the physical environment of the computer
– Includes things such as keystroke timing patterns, disk
electrical activity, mouse movements, and instantaneous
values of the system clock
– The source, or combination of sources, serve as input to
an algorithm that produces random binary output
– The TRNG may simply involve conversion of an analog source
to a binary output
– The TRNG may involve additional processing to overcome any
bias in the source
Pseudorandom Number Generator
(PRNG)
• Takes as input a fixed value,
called the seed, and produces
a sequence of output bits
using a deterministic algorithm
– Quite often the seed is
generated by a TRNG
• The output bit stream is
determined solely by the input
value or values, so an
adversary who knows the
algorithm and the seed can
reproduce the entire bit
stream
• Other than the number of bits
produced there is no
difference between a PRNG
and a PRF
Two different forms of PRNG
Pseudorandom
number
generator
• An algorithm that is
used to produce an
open-ended
sequence of bits
• Input to a symmetric
stream cipher is a
common application
for an open-ended
sequence of bits
Pseudorandom
function (PRF)
• Used to produce a
pseudorandom string
of bits of some fixed
length
• Examples are
symmetric
encryption keys and
nonces
PRNG Requirements
• The basic requirement when a PRNG or PRF
is used for a cryptographic application is that
an adversary who does not know the seed is
unable to determine the pseudorandom
string
• The requirement for secrecy of the output of
a PRNG or PRF leads to specific requirements
in the areas of:
– Randomness
– Unpredictability
– Characteristics of the seed
Randomness
• The generated bit stream needs to appear random
even though it is deterministic
• There is no single test that can determine if a
PRNG generates numbers that have the
characteristic of randomness
– If the PRNG exhibits randomness on the basis of
multiple tests, then it can be assumed to satisfy the
randomness requirement
• NIST SP 800-22 specifies that the tests should seek
to establish three characteristics:
– Uniformity
– Scalability
– Consistency
Randomness Tests
• Which of these sequences is more
random?
– 1110011010100100101010111100110001011
01001010
– 1111111000000111100001011111111000000
000001111
– The larger the lengths of runs of 1 and 0s are
the lesser the sequence would be random.
Randomness Tests
• SP 800-22 lists 15
separate tests of
randomness
Frequency test
• The most basic test
and must be included
in any test suite
• Purpose is to
determine whether
the number of ones
and zeros in a
sequence is
approximately the
same as would be
expected for a truly
random sequence
Runs test
• Focus of this test is the total
number of runs in the sequence,
where a run is an uninterrupted
sequence of identical bits bounded
before and after with a bit of the
opposite value
• Purpose is to determine whether
the number of runs of ones and
zeros of various lengths is as
expected for a random sequence
Three
tests
Maurer’s
universal
statistical test
• Focus is the number
of bits between
matching patterns
• Purpose is to detect
whether or not the
sequence can be
significantly
compressed without
loss of information.
A significantly
compressible
sequence is
considered to be
non-random
Unpredictability
• A stream of pseudorandom numbers should exhibit two forms
of unpredictability:
• Forward unpredictability
– If the seed is unknown, the next output bit in the sequence
should be unpredictable in spite of any knowledge of previous
bits in the sequence
• Backward unpredictability
– It should not be feasible to determine the seed from knowledge
of any generated values. No correlation between a seed and
any value generated from that seed should be evident; each
element of the sequence should appear to be the outcome of
an independent random event whose probability is 1/2
• The same set of tests for randomness also provides a test of
unpredictability
– A random sequence will have no correlation with a fixed value
(the seed)
Seed Requirements
• The seed that serves as input to the PRNG
must be secure and unpredictable
• The seed itself must be a random or
pseudorandom number
• Typically the seed is generated by TRNG
Generation
of
Seed
Input
to
PRNG
Algorithm Design
• Algorithms fall into two categories:
– Purpose-built algorithms
• Algorithms designed specifically and solely for the
purpose of generating pseudorandom bit streams
– Algorithms based on existing cryptographic
algorithms
• Have the effect of randomizing input data
Three broad categories of cryptographic algorithms are
commonly used to create PRNGs:
• Symmetric block ciphers
• Asymmetric ciphers
• Hash functions and message authentication codes
Linear Congruential Generator
•
An algorithm first proposed by Lehmer that is parameterized with
four numbers:
m the modulus
m>0
a
the multiplier
0 < a< m c the increment 0≤ c < m X0 the starting value, or seed 0 ≤ X0 < m • The sequence of random numbers {Xn} is obtained via the following iterative equation: Xn+1 = (aXn + c) mod m • • If m , a , c , and X0 are integers, then this technique will produce a sequence of integers with each integer in the range 0 ≤ Xn < m The selection of values for a , c , and m is critical in developing a good random number generator Blum Blum Shub (BBS) Generator • Has perhaps the strongest public proof of its cryptographic strength of any purposebuilt algorithm Choose two large prime numbers p and q that both have a remainder of 3 when divided by 4, i.e. p mod 4 = q mod 4 = 3 Next choose a random number (seed) s such that s is relatively prime to n. X0 = s2 mod n for i = 1 to infinity Xi = (Xi - 1)2 mod n Bi = Xi mod 2 Table 7.1 Example Operation of BBS Generator p = 383 q = 503 n = 192649 s = 101355 BBS Generator • BBS referred to as a cryptographically secure pseudorandom bit generator (CSPRBG) – A CSPRBG is defined as one that passes the next-bit-test if there is not a polynomial-time algorithm that, on input of the first k bits of an output sequence, can predict the (k + 1)st bit with probability significantly greater than 1/2 • The security of BBS is based on the difficulty of factoring n PRNG Using Block Cipher Modes of Operation • Two approaches that use a block cipher to build a PNRG have gained widespread acceptance: – CTR mode • Recommended in NIST SP 800-90, ANSI standard X.82, and RFC 4086 – OFB mode • Recommended in X9.82 and RFC 4086 Table 7.2 Example Results for PRNG Using OFB Table 7.3 Example Results for PRNG Using CTR ANSI X9.17 PRNG • One of the strongest PRNGs is specified in ANSI X9.17 – A number of applications employ this technique including financial security applications and PGP Input • Two pseudorandom inputs drive the generator. One is a 64-bit representation of the current date and time. The other is a 64-bit seed value; this is initialized to some arbitrary value and is updated during the generation process. The algorithm makes use of triple DES for encryption. Ingredients are: Output • The output consists of a 64-bit pseudorandom number and a 64-bit seed value. Keys • The generator makes use of three triple DES encryption modules. All three make use of the same pair of 56-bit keys, which must be kept secret and are used only for pseudorandom number generation. Ri = EDE([K1,K2], [Vi Å EDE ((K1,K2), DTi)]) Vi+1 = EDE([K1,K2], [Ri Å EDE ((K1,K2), DTi)]) Stream Ciphers Stream Cipher Design Considerations The encryption sequence should have a large period • A pseudorandom number generator uses a function that produces a deterministic stream of bits that eventually repeats; the longer the period of repeat the more difficult it will be to do cryptanalysis The keystream should approximate the properties of a true random number stream as close as possible • There should be an approximately equal number of 1s and 0s • If the keystream is treated as a stream of bytes, then all of the 256 possible byte values should appear approximately equally often A key length of at least 128 bits is desirable • The output of the pseudorandom number generator is conditioned on the value of the input key • The same considerations that apply to block ciphers are valid With a properly designed • A potential advantage is that stream ciphers that do not pseudorandom number generator a stream cipher can use block ciphers as a building block are typically faster and use far less code than block ciphers be as secure as a block cipher of comparable key length RC4 • A stream cipher designed in 1987 by Ron Rivest for RSA Security RC4 – Steps • • Initialization of S for i = 0 to 255 do S[i] = i; T[i] = K[i mod keylen] See next slide for pictorial representation Initial Permutation of S j = 0; for i = 0 to 255 do j = (j + S[i] + T[i]) mod 256; Swap(S[i], S[j]); • Stream Generation i, j = 0; while (true) i = (i + 1) mod 256; j = (j + S[i]) mod 256; Swap(S[i], S[j]); t = (S[i] + S[j]) mod 256; k = S[t]; Online demo: http://rc4.online-domaintools.com/ RC4 • Variable key size stream cipher with byte-oriented operations • Period is greater than 10100 • Based on the use of a random permutation • Eight to sixteen machine operations are required per output byte and the cipher can be expected to run very quickly in software • Used in the Secure Sockets Layer/Transport Layer Security (SSL/TLS) standards that have been defined for communication between Web browsers and servers • Is also used in the Wired Equivalent Privacy (WEP) protocol and the newer WiFi Protected Access (WPA) protocol that are part of the IEEE 802.11 wireless LAN standard Strength of RC4 A number of papers have been published analyzing methods of attacking RC4 • None of these approaches is practical against RC4 with a reasonable key length A more serious problem is that the WEP protocol intended to provide confidentiality on 802.11 wireless LAN networks is vulnerable to a particular attack approach • The problem is not with RC4 itself, but the way in which keys are generated for use as input • Problem does not appear to be relevant to other applications and can be remedied in WEP by changing the way in which keys are generated • Problem points out the difficulty in designing a secure system that involves both cryptographic functions and protocols that make use of them Summary • Principles of pseudorandom number generation • The use of random numbers • TRNGs, PRNGs, and PRFs • PRNG requirements • Algorithm design • Pseudorandom number generators • Linear congruential generators • Blum Blum Shub generator • Pseudorandom number generation using a block cipher • PRNG using block cipher modes of operation • ANSI X9.17 PRNG • NIST CTR_DRBG • Stream ciphers • RC4 • Initialization of S • Stream generation • Strength of RC4