Deniable Authentication with RSA and Multicasting
Daniel R.L.Brown∗
February24,2005
Abstract
A deniable authentication scheme using RSA is described and proven cure in the
random oracle model.A countermeasure to a well-known attack on efficient deniable
authentication to multiple recipients is described and proven cure.
1Introduction
Email and text messaging are single-pass media.Their authentication has therefore tradi-tionally ud digital signatures.But signatures leave evidence that third parties can verify. Sometimes this is undesirable and it is preferable to have deniable authentication instead. Indeed,while common n dictates to authenticate all messages,it also dictates to be very careful what you sign.
In deniable authentication,a nder Alice and a recipient Bob each have their own public keys.Alice nds an authenticated message to Bob using her private key and Bob’s public key.Bob verifies the authenticated message with his private key and Alice’s public key. Alice does this without digitally signing anything.Bob has no proof to others that Alice ud her private key to do anything.
Related concepts to deniable authentication are plausible deniability and prevention of surreptitious forwarding.The IETF S/MIME protocol,which can be ud to cure email, includes an AuthenticatedData type that does not include a signature,and is instead -cured with Diffie-Hellman key agreement[Hou99]or elliptic curve Menezes-Qu-Vanstone (ECMQV)[BWBL02].The term deniable authentication is also ud in[dRG05]for es-ntially the same notion as here.Less similar concepts are undeniable signatures and designated confirmer signatures.
Deniable authentication is straightforward with Diffie-Hellman(DH)key agreement and its derivatives such as ECMQV,at least for the ca of single recipients.Most(single-pass) authentication methods bad on Rivest-Shamir-Adleman(RSA)have,however,ud a conventional signature,and as such were not fully deniable.A deniable authentication scheme bad on RSA is described and proven cure under the standard RSA assumption and the random oracle model.It is also proved cure under a strong assumption about RSA and a milder assumption on hash functions.
In efficient multi-recipient deniable authentication,it is necessary not to permit a mali-cious recipient to modify the message for other recipients.This paper provides a mechanism to prevent this kind of attack.
∗Certicom Rearch
1
1.1Applications
Deniable authentication can be ud as part of a countermeasure against spam.If recipients insist that every message they receive is authenticated,then they can resist nder address spoofing.Once nder identities are reliable,nder addressfiltering can be more effective.
Against spam,deniable authentication has an advantage over signatures in that nders of mass recipient messages must authenticate parately for each recipient.Spammers thus incur a per-recipient disincentive.This can be combined with other techniques of adding a nder-side cost.
Another application of deniable authentication is the protection of nsitive organiza-tion data.Suppo such data is leaked outside the organization.If a signature has been applied to the dat
a,an outsider could ascertain that the data is authentic.If only deniable authentication was applied,however,then the outside could not be sure the leak was not fabricated.
1.2Standards
Existing standards for discrete logarithm bad key agreement,such as X9.42and X9.63, are already uful for deniable authentication.Indeed,they have already been ud in other standards,such as S/MIME,for deniable authentication.
On the other hand,standards for RSA generally do not provide(single-pass)deniable authentication.For example,the current draft of ANS X9.44gives two key agreement schemes using RSA and one key transport scheme.Both agreement schemes are derived from the protocol TLS.Thefirst key agreement scheme and the key transport scheme do not have bilateral authentication becau the nder does not have a public key.The cond key agreement scheme involves digital signatures,so full deniability is not possible.Deniable authentication would be a uful addition to standards like ANS X9.44.
Secure efficient deniable authentication with multiple recipients would be a valuable enhancement of standards that specify deniable authentication.The S/MIME standard is good example of this,particul
arly[BWBL02,Hou99].
1.3Previous Work
Several key establishment mechanisms using digital signatures and public key encryption are described in[MvOV95,§12.5.2].The schemes do not have full deniability when ud with digital signatures such as PKCS#1v.1.5and PSS.Even when ud with raw RSA digital signatures,they do not have full deniability becau identifiers are included in the signatures.(Incidentally,raw RSA digital signatures are weak in the n that existential forgery is easy.)
Triple-wrapping message,either by sign-encrypt-sign or encrypt-sign-encrypt,is not fully deniable authentication,becau Alice signs something that Bob can show to others. If the signed data is a ciphertext,Bob can generally reveal the plaintext and provide some additional data such that third parties can verify the correspondence of plaintext to cipher-text.In fact,with most encryption schemes,Bob can do this without even revealing his private key.If the ciphertext is only the encryption a symmetric authentication key,not a message itlf,then authentication is weakly deniable,in the n that Bob cannot prove Alice ud the symmetric authentication key on particular messages,but he can prove that Alice authenticated the key.
2
Some countermeasures to surreptitious forwarding,such as tho surveyed by Davis [Dav01],primarily aim to prevent forwarding only in the n that the ur’s regular cryp-tographic application cannot perform it.More active adversaries will not u conventional software,and instead u software that can extract the signatures.
2Scheme Ingredients
This ction defines the ingredients to the scheme.
2.1Some Notation for General Trapdoor Permutations
麦茬
The RSA primitive is a trapdoor permutation.The deniable authentication scheme described in this paper works for any trapdoor permutation.So,for the sake of generality,we u a generic notation for trapdoor permutations.Wefirst describe how the notation works in general,and then describe how it applies to RSA.
A trapdoor permutation pair is(N,n),where N is an easily computable public function and n=N−1is a private inver function.The function is n is easily computable only by the key pair owner.So,computi
ng n from the description of N is infeasible.Such a function N is called a trapdoor permutation and n is called its trapdoor inver.We may also call N and n the public key and private key,respectively,although this clashes slightly with the conventional terminology with RSA.
In the ca of RSA,the trapdoor key pair(N,n)is as follows.Let e be some public value,typically e=3or e=216+1.Let p,q be cret primes with gcd(e,(p−1)(q−1))=1. Let N be the function defined by N(x)=x e mod pq.In a slight abu of our own notation, we also write N=pq in line with conventional notation for RSA.The trapdoor inver is defined as n=N−1,so n(y)=y d mod N,where d=e−1mod(p−1)(q−1).In another abu of notation,we might write n for d.The pair(N,n)is an RSA key pair with public permutation N and private permutation n.
Although RSA is the most widely ud and known trapdoor permutation,others are known.One of the most important is Rabin-Williams(RW),who curity is known to be equivalent to the hardness of factoring.Our system will work with general trapdoor permutations.
Let[N]be the domain of the function N and let[n]be the domain of function n.For RSA,we can u[N]=[n]={x:0 x N−1,gcd(x,N)=1},as a subt of integers.In practice,it is equivalent to regard[N]for RSA as the t of integers in the interval[1,N−1].
Both Alice and Bob have key pairs.We write(A,a)for the key pair of Alice,and(B,b) for Bob’s key pair.Alice will generally be the nder and authenticator of the message, and Bob will generally be recipient and verifier of authenticated message.Each will have an authentic copy of the other’s public key.For further simplicity,we may also identify Alice and Bob with their public keys.The meaning of A and B as entity or public key(as trapdoor permutation or RSA integer)will be made clear,either from context or explicitly.
It will be efficiency in the trapdoor-bad deniable authentication scheme for two dif-ferent domains[A]and[B]to have significant overlap.For RSA functions,this is easily achieved if A and B are near in size.
For other intermediate values in the protocols,we generally u upperca letters for public values that anybody can determine and lowerca for cret values that only Alice or Bob can determine.This convention is similar to that ud with some kinds of public key cryptography.
3
2.2Key derivation functions
Established keys are derived from the established cret and other shared data using a key derivation function(KDF).Key derivation functions are constructed from hash functions. One construction is the KDF of ANS X9.63.The schemes described in this paper are such that the following data in the parameters strengthens the curity.
•Identifiers for Alice and Bob can be included in the key derivation parameters,which helps to thwart unknown key share attacks.Identifiers can be public keys or rep-rentations of names,or hashes of the latter.If symmetry is desired,so that the established key cannot be said to be directed from Alice to Bob,or vice versa,Al-ice and Bob’s identifier can be combined with a symmetric function such as integer multiplication.
写事的好词好句•Time or nonce values included in the key derivation function help to ensure freshness of the established key,which helps to ensure weak implicit entity authentication and known-key curity.
•A MAC tag can be include the key derivation function.This helps to avoid message tampering that might be possible in an efficient multi-recipient deniable authentication scheme.
2.3Intermediate Bijection
你这个大坏蛋
The curity of the deniable authentication may be enhanced with some cure bijections. The bijections should take a form such as S:β→αwhereβ⊆[b]andα⊆[a],with the subts containing almost elements of their superts.Both directions of the bijection should be easily computable.The bijection is afixed public algorithm,although it may optionally have a key.The bijection needs to be cure in a n similar to a cure hash function.Sofinding u and S(u)with a given a structure(independent of the definition of S)should be roughly as hard as doing so if S were a random bijection.For example,it should not be possible to make both u and S(u)small.In the curity analysis this helps to avoid an attack and to prove curity.
The cure bijection helps eliminates structure,such as small size,that an attack might exploit.Potentially,the bijection can be built from a block cipher,or possibly a key wrap function.The key can befixed for all applications of the scheme,or it could be lected dynamically,or made a function of the other values in the scheme.
2.4Message Authentication Code
A Message Authentication Code(MAC)is an algorithm that takes input of a message M and of cret key K,and then outputs a tag T=MAC K(M).Without knowledge of K,it should infeasible to compute th
e correct value T.In other words,a MAC is believed to be unforgeable.Parties that know K can nd a MAC tag T with the message M and then be sure that no other parties have modified the message M.
3RSA-Bad Schemes for Deniable Authentication
Deniable authentication is fairly straightforward with DH bad key agreement,as follows. Agree on a symmetric key,using a scheme that provides mutual authentication.Then apply
4
a (symmetric)message authentication code (MAC)to the message.This is the approach taken in S/MIME’s AuthenticatedData type.Esntially,the scheme here is the same.The interesting part is how RSA key agreement is done,in a single-pass,without signing anything.
A simplified version of the scheme is given in Figure 1.Alice nds Z =a (
B (x ))to Bob,where x is a random value that Bob can recover from Z as x =b (A (Z )).Alice and Bob can u x to derive a symmetric key k that they can u for any purpo,generally.In this ca,they u k to compute MA
C tag T on a message M .Alice nds M ,T ,and Z in a single pass.In lecting x ,Alice us a while loop to get an intermediate value Y =B (x )∈[a ],so that she can apply a .The purpo of this to ensure that Z and x do not have an bias that an attacker might be able to exploit.
Alice Bob
贫困户帮扶计划While(Y ∈[a ]):
x ∈R [B ]
Y =S (B (x ));
隋朝版图Z =a (Y )
k =KDF(x,A,B,T )
T =MAC k (M )
M,T,Z −−−−→Y =S −1(A (Z ))
接生过程x =b (Y )
k =KDF(x,A,B,T )
T ?
=MAC k (M )Figure 1:Simplified version of RSA message authentication
The scheme in Figure 1can be simplified by choosing S as the trivial identity function,and by not including identifiers in the key derivation function.This simplifications lead to some problems,however as noted below.
3.1A Forgery Attack Against Small RSA Exponents
When the trapdoor function is RSA with small values of e ,such as e =3,and the bijection S is the trivial identity function,the following attack is possible.Eve lects a value Z <e √e √From this Z ,Bob will computes x =b (S −1(A (Z )))=b (Z e )=Z .Eve knows x =Z ,and can derive k and compute T =MAC k (M ).She can thus forge Alice’s authentication.
(If Alice choos x randomly,there is negligible chance that she will generate such Z .)Although a suitable bijection S can easily prevents the forgery attack for small expo-nents,alternative countermeasures are possible.Larger exponents could be ud or Bob could just automatically reject
small values of Z .
3.2An Unknown Key-Share Attack
The simplified scheme is vulnerable to an unknown key share attack,which is a kind of an identity theft attack.In an unknown key-share attack,Eve replaces Alice’s identity with消防安全管理人
5
her own,making Bob think that Eve nt the message.(If Eve cannot stop the message from reaching Bob,then he will e identical messages from Alice and Eve.)In this attack, Eve cannot make Bob think Alice said something she did not.Eve cannot forge Alice’s authentication.
Eve can obviously authenticate M is nt in the clear,becau she can just authenticate M with her own public key E.In other words,the attack is only meaningful if M is somehow encrypted.Suppo that M was encrypted as C=ENC k(M).If M is encrypted and authenticated from Eve,that Eve must know the message and the message from be her.
Eve can launch the unknown key-share attack on the simplified scheme as follows.She computes Y=S−1(A(Z)).Then she computes Z =E(Z),where E is her public trapdoor function.She replaces(C,T,
Z)by(C,T,Z ).When Bob receives the modified message,it will appear to be from Eve.In a n the message is from Eve,becau Eve authenticated it,she just doesn’t know what the message is.
Inclusion of the identifiers of Alice and Bob in the key derivation function ems to pre-vent this attack.(Resisting unknown key share attacks is not primary objective of deniable authentication,so this property is not investigate in greater detail here.)Alternatively, Alice could encrypt Z as well as M,which also ems to prevent the attack becau Eve ems to need Z to get Y.
3.2.1Key Compromi Impersonation
If Eve obtains Bob’s private key b,she can impersonate anybody to Bob,including Alice. This is called key compromi impersonation in the context of key agreement schemes. Key compromi impersonation is true for any single-pass deniable authentication scheme, becau Bob is capable of producing validly authenticated messages,and thus so is Eve.
3.2.2Higher Iteration Variants
The scheme us an alternating application of Alice and Bob’s trapdoor and trapdoor inver functions,respectively.The scheme can be varied by applying the functions more often, such as:
Z=f(...B(a(B(x)))...)(1) where the outermost function f is a or B depending on whether the number of layers is even or odd.(The intermediate bijections have been omitted for simplicity.) The variants have more costly performance,but some may provide some different kinds of curity,as discusd later.(Some variants are completely incure,such as Z=B(a(x)).)
象棋将军怎么走4Security Analysis of the RSA Scheme
First,the simple proof of deniability is prented.Then some proofs of unforgeability (authenticity)are sketched.
4.1Deniability
To demonstrate the deniability of the scheme,we need to show that Bob could have generate the pair(Z,x)without Alice’s help.Bob can do this just by choosing random Z∈[A]and then computing x=b(A(Z)),repeating as necessary until Y=A(Z)∈[b].
6
