View page as slide show

CT30A8800 Secured communications

Pekka Jäppinen

Mostly following: Schneier, Applied Cryptography: Chapter 2

Digital signatures

  • Signature should be authentic. Signer has deliberately signed the document.
  • Signature should be unforgeable. Only the signer can do the signature
  • Signature should not be reusable.
  • It should not be possible to make changes in signed document i.e. document is unalterable
  • Signature cannot be repudiated i.e. signature should be undeniable.

Signature with symmetric cryptography

  • Arbitrator T shares secret keys , with A and B correspondingly
  • Key exchange has been done beforehand and the keys can be used several times
    • 1. A encrypts her message to B with and sends it to T
    • 2. T decrypts the message with
    • 3. T adds piece of information to message that states it was created by A and saves the message in database
    • 4. T signs the message with and sendss it to B
    • 5. B Decrypts the message and reads it.
  • • If B wants to show the signature to C he has to contact arbitrator T
  • 1. B encrypts the message with and sends it to T
  • 2. T decrypts message
  • 3. T verifies from the database that the original message came from A
  • 4. T encrypts the message with and sends it to C along with the A:s identity
  • 5. C decrypts and checks the message
  • Strengths of the protocol
    • Signature is authentic, unforgeable, not repudiable and it cannot be re-used
    • The signed document cannot be altered
  • Weakness of the protocol
    • Creating T is hard
    • T has to be trusted totally (T gets all the messages and T can sign documents in anyones name)
    • T:s database has to be enormous. (use of hashes can help a bit)
    • Requires too much time from T
    • Dependable on T → T is bottleneck and single weak spot.

Signatures with asymmetric cryptography

  • 1. A Calculates hash from a message
  • 2. A encrypts the hash with her secret key
  • 3. A sends the encrypted has to B
  • 4. B decrypts the hash with the public key of A and compares it to the hash he calculated from the received message
  • Strengths of the protocol
    • T is only required for verifying the public key
    • Signature is authentic, unforgeable, not repudiable and it cannot be re-used
    • The signed document cannot be altered
  • Benefits from hash
    • Signature can be stored separately from the actual document
    • Signature doesn't take too much space
    • Archive system can verify the existence of the document without saving it.
    • A can verify her rights to the document, even is she keeps the document secret for now (copyright, patents)
  • Weaknesses
    • B can cheat in some cases.
      • Same document can be reused (contract vs. check)
  • Timestamp
    • Timestamp can be bonded on e.g. day or time
      • In some cases just serial number is enough.
    • The timestamp can be used to verify if the document has already been handled
    • Document should be signed after the timestamp has been added.

Multiple signatures for one document

  • A signs document (or hash) after which B signs the document signed by A and so on.
    • In order to verify single signature, all the signatures has to be verified
    • Signing separate copies of the document
  • The actual document size grows
    • Signing hash of the document separately
  1. A signs hash
  2. B signs hash
  3. B sends signed hash to A
  4. A sends signatures and the document to C
  5. C verifies the signatures of A and B
  • Steps 1 and 2 can be done in parallel
  • In step 5 it is possible to verify just single signature


  • A signs message and later claims she has not done the signature
  1. A signs document
  2. A publishes her private key anonymously
  3. A claims that the signature has been done with the compromised key
  • Timestamps can limit the effects
    • A can claim the key has compromised earlier
    • A has to have good timing
  • Keys are stored in tamper-resistant modules (e.g. FineID-card)
    • The module does all the operations with the key
    • The use of private key requires password.
    • A has no access to the private key therefore she cannot publish it.
  • General protocol to avoid repudiation of signatures after long time
  1. A signs message
  2. A generates header where is identifying information about her.
  3. A combines the header to the signed message and signs the whole thing
  4. A the message with identity to T
  5. T verifies signature and confirms A's identity. T adds timestamp to both timestamp and A's identity, signs everything and then sends it all to both A and B
  6. B verifies signature of T identifying information and the signature of A
  7. A verifies the message that she sent to B. If she didn't sent the message she has to react quickly.

Signatures and encryption

  • Secure envelope
    • Encryption quarantees privacy
    • Signature quarantees authenticity
  • In real world
    • envelope guarantees privacy
    • signature guarantees authenticity
  • Signing before encrypting
    • Natural: The message is signed, not the envelope
    • Signature cannot bee verifies without decrypting the message
    • In legal terms, signed message can be compared for signing blindly
    • There is ways to attack the signature if eencrypted message is signed (see the asymmetric crypto lectures)
  • Different key pairs can be used for signing and encrypting
  • Benefits from two key pairs
    • The secret key for encryption key pair can given to authority , (key escrow)
      • signing key is still valid.
    • The size of the keys can differ as well as their validity time

Resending message as receipt

  • Let's assume that after B gets the message he sends the message back as a receipt to A.
  1. A signs message and encrypts it with B's public key and sends to B :
  2. B decrypts the message and verifies the signature
  3. B signs the message and encrypts it with the public key of A and sends it to A
  4. A decrypts the message and verifies the signature. if message and signature matches A knows B got the message correctly
  • Some communication protocols send automaticly receipt of the message
  • If encryption and signature are done with same algorithm and same keypair the system can be attacked since making signature equals to decryption
  • For example
    • M is one of the users of the system with own keys
    • M saves message that A send to B
    • M sends the saved message to B as her own message
    • B believes the message to be normal message and thus decrypts it and verifies signature automatically
    • Even though the decrypted message is meaningless B sends the receipt about arrived message to M according to protocol
  • Now all Mallory has to do is:
  1. Decrypt message with her own private key
  2. Encrypt (verify signature) with B's public key
  3. Decrypt (sign) message with her own private key
  4. Encrypt (verify signature) message with A's public key
  5. Thus Mallory has resolved the content of message M.
  • If the message had been checked before sending receipt, there would have been no problem
  • More evolved versions of the attack exists
  • do not sign or decrypt arbitrary messages and give the results to other people
  • Countermeasures
    • Use different keys for signing and encryption
    • use timestamps
    • Use hash functions

non transferable/undeniable signatures

• Normally the signature can be copied as is and shown to others and everyone can verify the signature

– Can be used for blackmailing or causing embarrassment

• Solution: signature that can be proved to be valid but cannot be be shown to third party without signers consent.

• Generic model:

1. A present signature to B

2. B generates random number that he send to A

3. A makes calculations with secret key and random number, then send the result to B. A may only do these calculations if the signature is right

4. B verifies the signature

• Chaum's undeniable signature algorithm

– public values for signature

∗ p = prime, g = primitive element

– A has

∗ secret key x

∗ public key

– A signs message by calculating

– Signature verification

1. B selects two random numbers a and b, which are smaller than P

2. B sends to A i.e. the signature raised to power of a and public key raised to power of b mod p

3. A calculates and sends to B

4. B verifies that

– B cannot proof to C that A has signed the message

∗ C may not be sure if the number B uses are random or if B has calculateed the numbers so that signature looks valid

– Chaum is not perfect

∗ for example chess master problem is still valid

– Beneficial for protecting privacy and digital rights

• There also exists a model in which A caan proof she has not made the signature

• Entrusted undeniable signature

– Only third party (judge) may do the disavowal procedure

– Signer cannot be forced to testify that she has not signed the message cause she cannot do that.

Designated confirmer signature

• All the workers in company can sign documents with undeniable signature but C does the verification

• compromise between normal and undeniable signature.

• A may not misuse the undeniable signature (for example to send out comapny secrets)

– C may do the validation even if A claims that the key is lost or just refuses to validate (or is not available to validate) the signature

• Protects A's signatures if she losees her key, is away or dies.

• Signature office

– C publishes his public key and people can designeate him to be verifier of signatures

– C takes more payment for each validation

– C can be for example patent office

Proxy Signature

• Proxy signatures allow designation of signature creation to certain person in original signers name, without revealing password.

– Example: A goes for a trip and B has to be able to sign important contract.

• Desired attributes

– Distinguishability

∗ proxy signature has to be distinguishable from normal signature by anyone

– Unforgeability

∗ only original signer and proxy signer can create valid proxy signature

– Proxy signer's deviation

∗ proxy signer cannot create signature that cannot be detected as proxy signature

– Verifiability

∗ verifier can be convinced that original signer agrees the signature

– Identifiability

∗ original signer can determine the proxy signer from proxy signature

– Undeniability

∗ proxy signer cannot disawov the signatures he has made

Group signature

• Member of the group can create signature so that:

– Receiver can verify that the signature is from the correct group

– Receiver cannot find out who from the group signed the message

– In case of problem trusted party can reveal the correct signer

1. Trent generates lot of key pairs and gives list of key pairs to each of the members of the group

2. Same key pair is not in more than one list

• If the is m members in the group and everyone has n key pairs then total amount of key pairs is n * m

3. Trent publishes the public keys of the group in random order, but keeps the information who has which key as a secret.

4. When member of group wants to sign a document he chooses random key from list and does the signature

5. When someone wants to verify if the signature is done in the name of group, he uses the published public keys and sees if one of those works. (or the correct public key might be informaed in the message)

6. T can reveal the owner of the key if problem arises.

• Weaknesses

– Requires T

– T knows all the keys (can create signatures in anyones name)

– Requires lot of keys

– Adding one new user is not simple (adding new keys reveals the newcomer)

– Other protocols have been published (maybe someone will keep seminar about signaturee protocols?)

Timestamp services

• To prove the creation or signing moment of the document

• Properties

– No dependency pn physical media

– Timestamped document should be unchangeable

– Timestamp should be unchangeable and it cannot be replaced with new timestamp

• Arbitrator approach

1. A sends a copy of document to T

2. T saves the document and the time of arrival of the document

– Problem

∗ Document can be read by T

∗ Document can be stolen during transmission to T

∗ Document repository of T will grow too big in time

∗ Document may get corrupted during or after transmission → Integrity check is required

∗ T has to be trusted

• Enhanced version

1. A sends T the hash about the document to be timestamped

– Now T has no knowledge about the document contents and the document cannot be eavesdropped during transmission

2. T combines hash and the time of arrival

3. T signs the result and sends it back to A

– T does not store any copy, thus he does not need own repository

4. A checks signature, hash and timestamp

– Transmission errors are caught

– Remaining problems

∗ Trust towards T. A and T together may create any timestamp they wish

• Linked protocol

– A's timestamp is linked to the timestamps T has generated earlier. A and T can change the time not earlier than the previous timestamp T made

1. A sends T n:th hash and identity .

2. T sends to A , where is arrival time of and

3. When Tstamps next document he sends to A i.e. informs A whose document is stamped after A

• Distributed protocols

1. Using the stampable hash H as an input A generates random numbers with cryptographicly safe PRNG

2. A selects identities corresponding to these generates numbers from a predetermined table and sends the hash H to these people.

3. Recipients timestamps and signs the hash and sends it back to A

– for the fraud, A should make deal with all the signing parties

Attacks against RSA signatures

• Chosen ciphertext attack 1: E wants to know what A has sent.

– E listens A:s communications and gathers ciphertext c encrypted with RSA.

– E wants to know what message m contains: – E chooses random number r, which is smaller than n and fetches A's public key e – E calculates: – when , then – If E can make A sign y, i.e. decrypt the encryption, E gets from A the message: – – Now E can calculate

• Chosen ciphertext attack 2: M wants T to sign message that T wouldn't normally sign

– let the message to be signed be m' – M chooses random number x and calculates – M sends m to T for signing – T returns – M calculates which is signed m' – Attack uses the weakness • Chosen ciphertext attack 3: M wants T to sign message which A normally wouldn't sign – M generates two messages so that and sends to A for signing – A signs messages and : and – M counts

• Attack against encryption and signing with RSA if message is signed after encryption – A send message to B first encrypting it with B's public key and then signing it with her own private key – if B wants to claim that A sent him message m' instead of m, he calculates value x from formula – After that B states that his public key is and public modulus is and thus can state A signed message m'

Lessons from RSA attacks

• Don't sign whole messages, just the hashes. – Use different keys for signing and encrypting. • Messages should be padded to avoid risk from small encryption exponent • Sign message before encryption. – Sign message not envelope.

Last modified: 2014/02/10 21:54