Mostly following: Schneier, Applied Cryptography: Chapter 2
• 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 paraller
∗ 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 omdule 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 geneerates 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.
• 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
• 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 Aa'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
– Use different keys for signing and encryption
– use timestamps
– Use hash functions
• 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.
• 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 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
∗ proxy signature has to be distinguishable from normal signature by anyone
∗ 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
∗ verifier can be convinced that original signer agrees the signature
∗ original signer can determine the proxy signer from proxy signature
∗ proxy signer cannot disawov the signatures he has made
• 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.
– 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?)
• To prove the creation or signing moment of the document
– 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
∗ 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
• 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'
• 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.