View page as slide show Export page to Open Document format

CT30A8800 Secured communications

Pekka Jäppinen

Following mostly Schneier: Applied Cryptography


  • Three basic models
  • 1. Something you know
    • Password, PIN
  • 2. Something you are
    • Physical features, involuntary behavior, signatures (physical)…
  • 3. Something you have
    • Magnetic cards, keys, password generators

Goals for authentication protocols

  • A can prove to be A
  • B cannot use A's proof to impersonate A
  • C cannot impersonate A

Choices for authentication protocols

  • Reciprocity of authentication
    • Both communication partners authenticate themselves vs. only one side is authenticated
  • Efficiency
    • Calculation (How many operations are needed)
    • Communication (How many messages)
  • Secret storing
    • Handling of key material
  • Third party
    • Required / not required
    • Real time use (e.g. automatic key exchange device)
    • Level of trust (Stores secret/public key)
  • Nature of proof
    • Verifiable proof
    • zero-knowledge proof

Password authentication

  • Traditional password authentication
    1. User gives password
    2. Computer compares the given password to the one stored in database
    3. Weakness: password storage
  • Password stored read protected in the service (weak solution)
    • Anyone who can have access to the password file can read passwords
  • Storing encrypted password
    • Password is encrypted or hash value is calculated from it and the result is stored in database. When user wants to be authenticated the same function is used and the result is compared to the result stored in database.

Attacks against password input

  • Sniffing
  • Eavesdropping, van eck
  • Social engineering
  • Trojans

Brute-force attack against encrypted password storing

  • Brute-force attack
    • Calculate all possibilities and find the match
  • Brute-force can be slowed down in two ways
  • 1. Slowing down the calculating
    • Run the encryption algorithm several times
    • Slows down the password checking n-times, where n is the amount of used rounds.
    • Brute-force slows also down n-times
  • 2. Using seed.
    • Add seed in the password before calculating hash. When user gives password, hash is calculated with all the possible seeds.
    • Requires 2^{Seed} additional calculations, when password validity is checked.
    • Brute-force attack with n-bit password requires average of \frac{2^{n+seed}}{2} calculations i.e. 2^{Seed} times more calculations than without seed
    • Password is more secured, but authentication is slower
    • Passphrases are usually easier to remember and hold enough entropy to complicate brute-force attack

One time passwords

  • password lists. The list may base to one-way function
  • SKEY
    • A provides random number, R
    • Computer calculates x_{0}=f(R),x_{1}=f(f(R)),\ldots,x_{101}=f(f\ldots f(R)\ldots) . x_{101}is stored at the computer while user is sent the list x_{i} , i=0..100
    • When user wants to authenticate he provides value x_{100} and removes the value from list (draws cross over).
    • Computer calculates f(x_{100}) and compares the result to the stored value (x_{101}). If values match user is authenticated and x_{100} is stored at computes
  • SKEY security bases on the one-way ness of function f i.e. one cannot calculate x_{i-1} from x_{i}

Challenge-response authentication

  • Authentication is proved by stating the knowledge about the secret without revealing it.
  • With Asymmetric cryptography:
    • 1. A device generates random bits and sends them to A
    • 2. A encrypts the bits using private key and returns the results with her name
    • 3. device fetches the public key of A from database and decrypts the message
    • 4. If the decrypted message matches to original generated one, A is authenticated.
  • Pros:
    • A does not have to send any secrets over unsecure line
    • Connection doesn't require secured connection
  • Weaknesses
    • Asymmetric private key has to be stored on somewhere.
    • Only one side is authenticated. Encrypting random bitstream is a risk →selected plaintext attack.
    • Encrypting with secret key == digital signature

General model for safe challenge-response protocol

  1. A makes some calculations based on random numbers and private key. The results is sent to B.
  2. B sends some random number to A
  3. A makes some calculations based on all the random numbers and private key. The result is sent to B
  4. B makes calculations based on A:s public key and the results A sent. The calculations confirm that A knows the private key corresponding to the known public key of A.

zero-knowledge proof of identity

  • We want to proof we know a secret without giving up any information about the secret itself
  • The proof cannot be shown later on to other parties.
  • Cut and choose protocol
    • Cutting the bread: A divides the bread and B chooses which piece he takes.

Magic cave example

  • 1. V is on the cave entrance from where he cannot see to first crossing
  • 2. P enters the cave and goes either to left or right tunnel from the crossing. Left and right tunnels are connected deeper in the cave but in between them, there is a magic door which can be only opened with magic word.
  • 3. When P has walked to the door, V enter the cave and walks to the crossing
  • 4. V shouts in to the cave and tells P to come out from either left or right tunnel
  • 5. P follows the orders and use the magic word if necessary
  • 6. The procedure is repeated n-times, to guarantee P knows the magic word
  • Chance for making right guess when choosing the tunnels is 50% (After 10 rounds the chance is \frac{1}{2^{10}}=\frac{1}{1024} )


  • Initial phase (done before hand):
    • 1. T Chooses and publishes value n=pq, but keeps primes p and q as a secret.
    • 2. A chooses secret s, which is prime number between values 1\leq s\leq n-1 and counts v=s^{2}mod\: n. Then A registers v to T as a public key (v is number between 0-(n-1))
  • Fiat-Shamir t-rounds
  • 1. A chooses random number r, 1\leq r\leq n-1 and counts x=r^{2}mod\: n , which is sent to B
  • 2. B chooses challenge bit e, which is either 0 or 1 and sends the challenge to A
  • 3. A calculatesy=r*s^{e}mod\: n and sends to B (if e=0\Rightarrow y=r )
  • 4. B rejects answer if y=0(to disallow r = 0 trick) but otherwise accepts the answer if y^{2}\equiv x*v^{e}mod\: n .
  • Challenge e=1 verifies that A knows secret s. Challenge e=0 verifies that A cannot cheat by choosing suitable x.
    • if A tries to cheat and sends x=r^{2}/v he can provide correct answer to challenge e=1 by sending y=r, (y^{2}=\frac{r^{2}}{v}*v^{1}mod\: n=r^{2})
    • To challenge e=0 A should be able to calculate \sqrt{r\:}mod\: n
  • At best the A can answer correctly to one of the questions, thus possibility for cheating is 50% per round
  • B cannot determine anything about secret s, since B do not know the random number r.
    • Only thing B knows about s is v=s^{2}mod\: n

Attacks against zero knowledge proof of identity

  • Chessmaster problem: A works as man in the middle
  • Mafia trick: B and C co-operate against A.
  • Exact timing can protect from these attacks.
    • Fraud with multiple identities
  • Person generates more than one public key
    • To prevent this fraud, a method for guaranteeing person has just one identity (one public key for authentication) is required
    • Passport renting
  • Private key is compromised i.e. given to friend or criminal
    • In challenge-response authentication the actual identity is not validated just the fact that the person authenticated knows the secret (private key)
    • Biometric authentication is need to guarantee the identity

Token based authentication

  • Token can be used for authentication in challege-response model i.e. the token handles thee response to the challenge.
  • For example: Finnish electronic identity card (FINEID) contains the information about the user, goverment certified public keys for encyption and authentication and corresponding private keys.
  • Token based challenge-response.
    • 1. Token contains secret key and corresponding public key is at server. Token either encrypts or decrypts challenge and sends response.
    • 2. The challenge is fed into the token, which then caluculates the response
    • 3. Token contains time dependent function that is known also by the server. i.e. the authentication is based on time
  • Reliability is based on the fact that token cannot be reverse engineered.
    • Token verifies that the given token is used, not the identity of the token user.
    • It is possible to use biometrics or passwords along with token to provide more secure solutions.


  • Biometrics can be used to authenticate user locally
  • Biometrics can be used to protect the asymmetric cyrptography private key stored in token or computer.
  • Actual use of biometric reader has to be verified or similar risks exists as for passwords.

Authentication systems

  • Lot of different types of protocols: Kerberos, radius, wide-mouth frog, yahalom…
  • Kerberos (based on needham-shroeder protocol)
  • The goal is to provide access to different types of services and machines with single authentication.
  • Three different actions
    • 1. Authentication service, AS
    • 2. Ticket Granting Service, TGS
    • 3. Authenticating to service
  • Before anything else Alice has created a long term key <math>A_{k}<\math> for the system that is stored by Trent (KDC).
    • <math>A_{k}<\math> is hash value of users password.
  • Authentication service:
    • 1. Alice logs in to her workstation
    • 2. Workstation connects to Trent and requests session key for Alice. Request contains the identity of Alice <math>I_{A}<\math> and a timestamp T which are encrypted with Alice's long term key<math>A_{k}\math> : <math><\math>
  • 3. Trent responds with Ticket Granting Ticket (TGT) that contains identity of Alice<math>I_{A}<\math> , ticket validity time L, identity of Trent <math>I_{T}<\math> and Alice's key <math>K_{A}<\math> encrypted with Trent's key <math>K_{T}<\math> :<math>E_{K_{T}}(I_{A},L,I_{T},K_{A})<\math> . Trent also sends new session key <math>K_{A-T}<\math>, that is used for communications between Trent and Alice encrypted with Alice's key <math>K_{A}<\math> <math>E_{K_{A}}(K_{A-T})<\math>


  • Ticket Granting Service (Alice wants to make connection to Bob)
  • 1. Alice sends TGT to Trent along with Bob's identity encrypted with session key <math>K_{A-T}<\math>
  • 2. Trent generates timestamp T, validity time L, secret key <math>K_{A-B}<\math> and encrypts these along with Alice's identity <math>I_{A}<\math> using the key Trent has shared with Bob <math>E_{K_{B}}(T,L,K_{A-B},I_{A})<\math> . This is a ticket for Alice to use Bob's service. Trent also sends to Alice the generated information and Bob's identity encrypted with Alice's long term key <math><E_{K_{A}}(T,L,K_{A-B},I_{B})\math> . Trent sends these to Alice.
  • 3. Alice decrypts the information and stores it.
  • Authentication to service
    • 1. Alice encrypts message containing her own identity <math>I_{A}<\math> and timestamp T with key <math>K_{A-B}<\math>: <math>E_{K_{A-B}}(I_{A},T)<\math>. Alice sends the encrypted message to Bob along with the ticket gained from Trent <math>E_{K_{B}}(T,L,K_{A-B},I_{A})<\math> .
    • 2. Bob decrypts the message and verifies Alices Identity. If everything matches Bob lets Alice to use his service.

Things learned from authentication systems development and evaluation

  • When system is optimized important aspects are easily forgotten and security is weakened
  • It is easy to get lost when doing optimization. For example, if you don't have authentic time, you can't use one.
  • When choosing the used protocol it is important to understand the environment where protocol is used. What do wwe want to optimize?
  • Usually it is better to use good and well known model instead of creating your own.
    • More about authentication: Richard E. Smith: Authentication, from passwords to public keys
Last modified: 2013/07/01 14:42