CHAPTER 12: From Crypto-Theory to Crypto-Practice I

                         CRYPTOANALYSIS  of linear feedback shift registers

                                         Linear Recurrences

Linear feedback shift registers are an efficient way to realize recurrence relations of the type

 

        x[n+m] = c[0] x[n] + c[1] x[n+1]+ … + c[m-1] x[n+m-1   ] (mod n)



that can be specified by 2m bits c[0] ,  … , c[m-1]  and x[1] ,  … , x[m].

                                     Finding Linear Recurrences



To test whether a given portion of a key was generated by a recurrence of length m if we know x[1] ,
… , x[2m ] we need to solve the matrix equation















and then to verify whether remaining available bits x[2m+1] ,  …  are really generated by the
recurrence obtained.

[

                                    ]Finding Linear Recurrences

The basic idea to find linear recurrences generating a given sequence is to check whether there is
such a recurrence for m = 2, 3, … In doing that we use the following result.

Theorem  Let









If the sequence x[1] , x[2] , … , x[2m-1 ] satisfies a linear recurrence of length less than m, then
det(M) = 0.

Conversely, if the sequence x[1] , x[2] , … , x[2m-1 ] satisfies a linear recurrence of length m and
detM = 0, then the sequence also satisfies a linear recurrence of length less than m.

                              How to make cryptoanalysts' task harder?

                                      Confusion and difussion

Two fundamental cryptographic techniques, introduced already by

Shannon, are confusion and diffusion.



Confusion obscures the relationship between the plaintext and the

ciphertext, which makes much more difficult a cryptanalyst’s attempts

to study cryptotext by looking for redundancies  and statistical

patterns. (The best way to cause confusion is through complicated

substitutions.)



Diffusion dissipates redundancy of the plaintext by spreading it over

cryptotext - that again makes much more difficult a cryptanalyst’s

attempts to search for redundancy in the plaintext through

observation of cryptotext. (The best way to achieve it is through

transformations that cause that bits from different positions in

plaintext contribute to the same bit of cryptotext.)



Mono-alphabetic cryptosystems use no confusion and no diffusion.

Polyalphabetic cryptosystems use only confusion. In permutation

cryptosystems only diffusion step is used. DES essentially uses a

sequence of confusion and diffusion steps.







                                 Cryptosystem  DES and its history

15. 5. 1973 National Burea of Standards published a solicitation for a new cryptosystem.



This led to the development of so far the most often used cryptosystem



                                   Data Encryption Standard - DES



DES was developed at IBM, as a modification of an earlier cryptosystem called Lucifer.



17. 3. 1975 DES was published for first time.



After a heated public discussion, DES was adopted as a standard on

15. 1. 1977.



DES used to be  reviewed by NBS every 5 years.

                        DES cryptosystem -  Data Encryption Standard - 1977

                        DES cryptosystem -  Data Encryption Standard - 1977

                                          How fast is DES?

                                        The DES controversy



1. There have been suspicions that the design of DES might contain hidden “trapdoors'‘ what allows
NSA to decrypt messages.



2. The main criticism has been that the size of the keyspace, 2 ^56 , is too small for DES to be
really secure.



3. In 1977 Diffie+Hellamn sugested that for 20 milions$ one could build a VLSI chip that could
search the entire key space within 1 day.



4. In 1993 M. Wiener suggested a machine of the  cost 100.000$ that could find the key in 1.5 days.

                                   What are key elements of DES?

  • A cryptosystem is called linear if each bit of cryptotext is a linear combination of bits of
plaintext.



  • For linear cryptosystems there is a powerful decryption method - so-called linear cryptanalysis.



  • The only components of DES that are non-linear are S-boxes.

 

  • Some of original requirements for S-boxes:

    – Each row of an S-box should include all possible output bit    combinations;

    – It two inputs to an S-box differ in precisely one bit, then the output must differ in a
minimum of two bits;

    – If two inputs to an S-box differ in their first two bits, but have  identical last two bits,
the two outputs have to be distinct.



  • There have been many other very technical requirements.



                                         Weaknesses of DES

  • Existence of weak keys: they are such keys k that for any plaintext p,

                                         E[k](E[k](p)) = p.

    There are four such keys:

    k Î {(0^28, 0^28), (1^28, 1^28), (0^28, 1^28), (1^28, 0^28)}



  • The existence of semi-weak key pairs (k[1], k[2]) such that for any plaintext

                                        E[k1](E[k2](p)) = p.



  • The existence of complementation property

                                     E[c(k)](c(p)) = c(E[k](p)),

     where c(x) is binary complement of binary string x.



                                       DES modes of operation

                                   8-bit VERSION of the CFB MODE

In this mode each 8-bit piece of the plaintext is encrypted without having to wait for an entire
block to be available.

The plaintext is broken into 8-bit pieces: P=[P[1],P[2],…].

Encryption: An initial 64-bit block X[1] is chosen and then, for j=1,2,… , the following computation
is done:

                              Advantages of different encryption modes

  • CBC mode is used for block-encryption and also for authentication;

  • CFB mode is used for streams-encryption;

  • OFB mode is used for stream-encryptions that require message authentication;



                                              CTR MODE

Counter Mode - some consider it as the best one.

Key design: k[i] = E[k](n, i) for a nonce n;

Encryption: y[i] = x[i] AA k[i

]This mode is very fast because a key stream can be parallelised to

any degree. Because of that this mode is used in network security

applications.



                                      Killers and death of DES



  • In 1993 M. J. Weiner suggested that one could design, using one million dollars, a computer
capable to decrypt, using brute force, DES in 3.5 hours.



  • In 1998 group of P. Kocher designed, using a quarter million of dolars, a computer to decrypt
DES in 56 hours.



  • In 1999 they did that in 24 hours.



  • It started to be clear that a new cryptosystem with larger keys is badly needed.



                                 Product- and Feistel-cryptosystems

Design of several important practical cryptosystems used the following three general design
principles.



A product cryptosystem combines two or more crypto-transformations in such

a way that resulting cryptosystem is more secure than component transformations.



An iterated  block cryptosystem iteratively uses a round function (and it has as parameters number
of rounds r, block bit-size n, subkeys bit-size k) of the input key K from which r subkeys K[i] are
derived.



A Feistel cryptosystem is an iterated cryptosystem mapping 2t-bit plaintext (L[0],R[0]). of t-bit
blocks L[0] and R[0] to a cryptotext (R[r],L[r]), through an r-round process where r >0.



For 0<I<r+1, round i maps (L[i-1],R[i-1]) to (L[i],R[i]) using a subkey K[i] as follows

                             L[i]=R[i-1],  R[i]=K[i-1]+f(R[i-1],K[i]),

where each subkey K[i] is derived from the main key K.



                                              Blowfish

  • Blowfish is Feistel type cryptosystem developed in 1994 by Bruce Schneider.

  • Blowfish is more secure and faster than DES.

  • It encrypts 8-bytes blocks into 8-bytes blocks.

  • Key length is variable 32k, for k = 1, 2, . . . , 16.

  • For decryption it does not reverse the order of encryption, but it follows it.

  • S-boxes are key dependent and they, as well as subkeys are created by repeated execution of
Blowfish enciphering transformation.

  • Blowfish has very strong avalanche effect.

  • A follower of Blowfish, Twofish, was one of 5 candidates for AES.

  • Blowfish can be downloaded free from the B. Schneider web site.



                                          AES CRYPTOSYSTEM

                                       ARITHMETICS in GF(2^8)

The basic data structure of AES is a byte



                       a = (a [7], a [6], a [5], a [4], a [3], a [2], a [1]),



where a[i]'s are bits, which can be conveniently represented by the polynomial



  a(x) = a [7] x ^7 + a [6] x ^6 + a [5] x ^5 + a [4] x ^4 + a [3] x ^3 + a [2] x ^2 + a [1] x + a
                                                [0].



Bytes can be conveniently seen as elements of the field



               F = GF (2 ^8) / m(x),     where   m(x) =  x ^8 + x ^4 + x ^3 + x + 1.





In the field F, the addition is the bitwise-XOR and multiplication can be elegantly expressed using
polynomial multiplication modulo m(x).



                 c = a AA b;     c = a · b     where c(x) = [a(x) · b(x)] mod m(x)

                                     MULTIPLICATION in GF(2^8)

Multiplication

                         c = a · b     where c(x) = [a(x) · b(x)] mod m(x)

in GF(2^8) can be easily performed using a new operation

                                            b = xtime(a)

that corresponds to the polynomial multiplication

                                    b(x) = [a(x) · x] mod m(x),

as follows



set c = 00000000 and p = a;



   for i = 0 to 7 do

    c  ¬ c AA (b[i] · p)

    p ¬  xtime(p)



Hardware implementation of the multiplication requires therefore one circuit for operation xtime and
two 8-bit registers.



Operation b = xtime(a) can be implemented by one step (shift) of the following shift register:

                                              EXAMPLES

                                      POLYNOMIALS over GF(2^8)

Algorithms of AES work with 4-byte vectors that can be represented by  polynomials of the degree at
most 4  with coefficients in GF(2^8).



Addition of such polynomials is done using component-wise and bit-wise  XOR.  Multiplication is done
modulo M(x)  =  x^4  +  1. (It holds x^J  mod  (x^4  +  1)  =  x^J ^mod 4.)



Multiplication of vectors

        (a[3]x^3  +  a[2]x^2  +  a[1]x  +  a[0])  Ä (b[3]x^3  +  b[2]x^2  +  b[1]x  +  b[0])

can be done using matrix  multiplication















where additions and multiplications (·) are done in GF(2^8)  as described before.



Multiplication of a polynomial a(x) by x results in a cyclic shift  of the coefficients.

                                         BYTE SUBSTITUTION

Byte substitution b  =  SubByte(a) is defined by the following  matrix operations























This operation is computationally heavy and it is assumed that it will be implemented by a
pre-computed substitution table.

                                         ENCRYPTION in AES

                                           KEY EXPANSION

The basic key is written into the state matrix with 4, 6 or 8 columns. The goal of the key expansion
procedure is to extend the number of keys in such a way that each time a key is used actually a new
key is  used.



The key extension algorithm generates new columns W[i] of the state matrix from the columns W[i -1]
and W[i -k] using the following rule



                                       W[i] = W[i -k] AA  V,



where

                F (W[i –1] ), if i mod k = 0

   V =       G (W[i –1] ), if i mod k = 4 and D[k] = 256 bits,

                W[i –1 ] otherwise



where the function G performs only the byte-substitution of the corresponding bytes. Function F is
defined in a quite a complicated way.

                                        STEPS of ENCRYPTION

AddRoundKey procedure adds byte-wise and bit-wise current key to the current contents of the state
matrix.

ShiftRow procedure cyclically shifts i-th row of the state matrix by i shifts.

MixColumns procedure multiplies columns of the state matrix by the matrix

                                         DECRYPTION in AES

                                           SECURITY GOALS



The goal of the authors was that Rijndael (AES) is K-secure and hermetic in the following sense:



Definition A cryptosystem is K-secure if all possible attack strategies for it have the same
expected work factor and storage requirements as for the majority of possible cryptosystems with the
same security.



Definition A block cryptosystem is hermetic if it does not have weaknesses that are not present for
the majority of cryptosystems with the same block and key length.

                                            MISCELANEOUS



Pronounciation of the name Rijndael is as “Reign Dahl'‘ or “rain Doll'' or “Rhine Dahl''.

                                    PKC versus SKC - comparisons

Security: With PKC, only one party needs to keep secret only one key; with SKC both party needs to
keep secret one key. No PKC has been shown perfectly secure. Perfect secrecy has been shown for
one-time pad and for quantum key distribution.

Longevity: With PKC, keys may need to be kept secure for (very) long time; with SKC a change of keys
for each session is recommended.

Key management: If a multiuser network is used, then fewer private keys are required with PKC than
with SKC.

Key exchange: With PKC no key exchange between communicating parties is needed; with SKC a
hard-to-implement secret key exchange is needed.

Digital signatures: Only PKC are usable for digital signatures.

Efficiency: PKC is much slower than SKC (10 times when software implementations of RSA and DES are
compared).

Key sizes: Keys for PKC (2048 bits for RSA) are significantly larger than for SCK (128 bits for
AES).

Non-repudiation: With PKC we can ensure, using digital signatures, non-repudiation, but not with
SKC.





                                          Digital envelops



Modern cryptography uses both SKC and PKC, in so-called hybrid

cryptosystems or in digital envelops to send a message m using a

secret key k, public encryption exponent e, and secret decryption

exponent d, as follows:







!!!!! missing figure

                                           KEY MANAGEMENT

                                     How are certificates used

                                            What is PKI?

                                       PKI users and systems

•    Certificate holder

•    Certificate user

•    Certification authority (CA)

•    Registration authority (RA)

•    Revocation authority

•    Repository (to publish a list of certicates, of revocated certificates,...)

•    Policy management authority (to create certification policy)

•    Policy approving authority

                                       SECURITY of CA and RA

PKI system is so secure how secure are systems for certificate authorities and registration
authorities.



The basic principles to follow to ensure necessary security of CA and RA.



•    Private key of CA has to be stored in a way that is secure against intentional professional
attacks.



•    Steps have to be made for renovation of the private key in the case of a collapse of the
system.



•    Access to CA/RA tools has to be maximally controlled.



•    Each requirement for certification has to be authorized by several independent operators.



•    All key transactions of CA/RA have to be logged to be available for a possible audit.



•    All CA/RA systems and their documentation have to satisfy maximal requirements for their
reliability.

                                PUBLIC-KEY  INFRASTRUCTURE  PROBLEMS

                            Main components of public-key infrastructure

                                           MAIN PROBLEMS

•    Authenticating the users: How does a CA authenticate a distant user, when issuing the initial
certificate?

(Ideally CA and the user should meet. Consequently, properly authenticated certificates will have to
be expensive, due to the label cost in a face-to-face identity check.)



•    Authenticating the CA: Public key cryptography cannot secure the distribution and the
validation of the Root CA's public key.



•    Certificate revocation lists: Timely and secure revocation presents big scaling and performance
problems. As a result public-key deployment is usually proceeding without a revocation
infrastructure.

(Revocation is the classical Achilles' Heel of public-key cryptography.)



•    Private key management: The user must keep his long-lived secret key in memory during his
login-session: There is no way to force a public-key user to choose a good password.

(Lacking effective password-quality controls, most public-key systems are vulnerable to the off-line
guessing attacks.)

                                     LIFE CYCLE of CERTIFICATES

                                       Pretty  Good   Privacy

In June 1991 Phil Zimmermann, made publicly available software that made use of RSA cryptosystem
very friendly and easy and by that he made strong cryptography widely available.



Starting February 1993 Zimmermann was for three years a subject of FBI and Grand Jurry
investigations, being accused of illegal exporting

arms (strong cryptography tools).



William Cowell, Deputy Director of NSA said: “If all personal computers in the world - approximately
200 millions - were to be put to work on a single PGP encrypted message, it would take an average an
estimated 12 million times the age of universe to break a single message''.



Heated discussion whether strong cryptography should be allowed keep going on. September 11 attack
brought another dimension into the problem.

                                SECURITY / PRIVACY REALITY and TOOLS



Concerning security we are winning battles, but we are loosing wars concerning privacy.



Four areas concerning security and privacy:



•    Security of communications – cryptography

•    Computer security (operating systems, viruses, …)

•    Physical security

•    Identification and biometrics



With google we lost privacy.

                                How cryptographic systems get broken

Techniques that are indeed used to break cryptosystems:

By NSA:

•    By exhaustive search (up to 2^80  options).

•    By exploiting specific mathematical and statistical weaknesses to speed up the exhaustive
search.

•    By selling compromised crypto-devices.

•    By analysing crypto-operators methods and customs.



By FBI:

•    Using keystroke analysis.

•    Using the fact that in practice long keys are almost always designed from short guessable
passwords.

                                          RSA in practice







•    660-bits integers were already (factorized) broken in practice.



•    1024-bits integers are currently used as moduli.



•    512-bit integers can be factorized with a device costing 5 K $ in about 10 minutes.



•    1024-bit integers could be factorized in 6 weeks by a device costing 10 millions of dollars.

                                   Patentability of cryptography

•    Cryptographic systems are patentable

•    Many secret-key cryptosystems have been patented

•    The basic idea of public-key cryptography are contained in U.S. Patents 4 200 770 (M. Hellman,
W. Diffie, R. Merkle) - 29. 4. 1980 U.S. Patent 4 218 582 (M. Hellman, R. Merkle)



The exclusive licensing rights to both patents are held by “Public Key Partners'' (PKP) which also
holds rights to the RSA patent.



All legal challenges to public-key patents have been so far settled before judgment.



Some patent applications for cryptosystems have been blocked by intervention of us: intelligence or
defense agencies.



All cryptographic products in USA needed export licences from the State department, acting under
authority of the International Traffic in Arms Regulation, which defines cryptographic devices,
including software, as munition.



Export of cryptography for authentication has not been restricted, Problems were only whith
cryptography for privacy.