Mostly following: Schneier, Applied Cryptography: Chapter 2
• 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.