Table of Contents
Introduction Definitions and context . . . . Issuer . . . . Applicant . . . . Identification token . . . . Reduced cost of highly secure electronic transactions . . . . Call centers . . . . Broad distribution of low cost software and electronic devices Preparation steps by the issuer . . . . The issuer gets a private/public key pair for a public key cryptosystem. . . . . The issuer prepares an applicant registration software. . . . . The issuer releases the applicant registration software. Preparation steps by the applicant . . . . The applicant obtains the applicant registration software. . . . . The applicant obtains a blank identification token. Computerized portion of the SAKEM procedure . . . . The applicant starts the registration software. . . . . The applicant chooses and types a pass query and a pass reply. . . . . The secret key is loaded in the identification token. . . . . The registration programs sends a registration request message to the issuer data processing center. . . . . The issuer data processing center receives the request, processes it and files the application request in the issuer database. Conversational portion of the SAKEM procedure . . . . A voice contact is established between applicant and issuer agent. . . . . The applicant and the issuer agent mutually verify the knowledge of pass query/reply by the other person in the conversation. . . . . The issuer agent verifies the identity of the applicant. . . . . The issuer agent flags the registration as being validated in the issuer database.
Outline / Operational / Strategy / Security / Programming
"SAKEM" stands for "Secret Authentication Key Establishment Method." It is useful for the issuance of electronic identification devices. While the present document covers the narrow and specialized cryptographic aspects of the SAKEM procedure, the document entitled "Information Security Principles of the SAKEM Procedure" takes a broader perspective on security management.
A public key cryptosystem (PKC) is at the heart of the proposed secret key establishment method. Among the PKCs that could fit the SAKEM procedure, only one is specified in the present document, namely the PEKE cryptosystem, see the article by Thierry Moreau, Probabilistic Encryption Key Exchange (in Electronics Letters, Vol. 31, number 25, 7th December 1995, pp 2166-2168). Two alternatives to the PEKE cryptosystem are compared in an hypertext document entitled "Public Key Cryptosystem Options for the SAKEM Procedure."
Provisions are made to exploit the PEKE efficiency as a public key cryptosystem for the applicant. There is an inconsequential modification to the PEKE cryptosystem suggested to fully exploit an optimisation technique known as the Montgomery method. This is described in an hypertext document entitled "Software Acceleration for Public Key Cryptography".
Notation:
<> represents inequality;
Outline / Operational / Strategy / Security / Programming
Outline / Operational / Strategy / Security / Programming
Outline / Operational / Strategy / Security / Programming
Outline / Operational / Strategy / Security / Programming
Outline / Operational / Strategy / Security / Programming
Outline / Operational / Strategy / Security / Programming
Outline / Operational / Strategy / Security / Programming
The PEKE cryptosystem public key is
N=P×Q, and the private key is
P,
Q, where the following conditions are essential:
N be a Blum integer, that is
N=P×Q, where
P and
Q are large prime numbers,
P<>Q,
P mod 4=3,
Q mod 4=3 (actually, Hugh C. Williams was the first to propose the use of
numbers of this form for cryptography, see his article
A Modification of RSA Public-Key
Encryption, in IEEE Transactions on Information Theory, Vol IT-26, no. 6,
November 1980, pp 726-729).
N should be at least 512 bits long. The same recommendation as with the
RSA cryptosystem apply here. We suggest
N to be 768 bits long.
Additional number-theoretic conditions are recommended:
P1=(P-1)/2,
P2=(P-3)/4,
Q1=(Q-1)/2, and
Q2=(Q-3)/4 are all prime numbers, and
P1 and
Q1 (in other words,
xP and
xQ do not exist for
2=xP² mod P1 and
2=xQ² mod Q1).
Actually, these two conditions guarantee the longest period (with an overwhelming probability) for the underlying [[Blum Blum & Shub]] pseudo-random number generator. The key point is to avoid short periods. The concern for short periods in the PEKE cryptosystem might be analogous to the threat of the "iterated encryption attack" against the RSA cryptosystem that was studied by Ueli Maurer in his article Fast Generation of Secure RSA-Moduli with Almost Maximal Diversity (in Advances in Cryptology, Eurocrypt '92, Lecture Notes in Computer Science, no. 658, Springer-Verlag, 1992, pp 636-647). The above recommended conditions are according to the general consensus on number-theoretic threats against public key cryptosystems before the work of Ueli Maurer was done. Ueli Maurer recommends that public key generation shouldn't be tweaked to account for number-theoretic threats. If this conclusion becomes accepted by practitioners of the RSA cryptosystem, the above recommended conditions might be reviewed (e.g. replaced by empirical testing of short periods generated by a given PEKE public key).
Normally, there is no need to obtain a security certificate for the public component of the issuer's private/public key pair. If the issuer already made arrangements for public key certification with a CA (Certification Authority), and if the CA offers a means to ensure the software integrity mechanism that is needed to protect the CA's public key, it may be reasonable to use the CA services. Still, the security offered by the presence of the CA in the picture is conditional to the applicant's ability to verify the CA's public key, and this is yet to be proven practical in the virus-prone personal computer environment.
In the preparation for later secret key establishment instances, the issuer gets a private/public key pair for itself, according to the PKC in use. See the PKC specification table under the row headings "Public key" and "Private key".
Outline / Operational / Strategy / Security / Programming
The PEKE cryptosystem requires issuer parameters in addition to the private/public key pair:
k and
t, where
k×t is the length of the SAKEM internal secret key,
1<=k<log2(N), we suggest
k=336/t with
t=2;
bn where
bn>N and
b is the natural computer word size (e.g.
b=232,
n=24 for
log2(N)=767);
S and
C, where
0<C×S<N, we suggest
C about 80 bits long, and
S odd from 8 to 64 bits long.
In the application of the Frogbit scheme for a semi-proprietary data integrity algorithm, it is important that the person who is authorized to use the data concealment utility checks the authenticity of every parameter in the set of issuer's parameters. In this context, secrecy is irrelevant; the important protection is to prevent malignant modification of the set of issuer's parameters in each and every software release.
In the software development process, the final stage of registration software preparation is the application of the Frogbit scheme for a semi-proprietary data integrity algorithm. This scheme is described in an hypertext document entitled "[[...]]." It is important that the person who is authorized to link object modules for the software release checks their authenticity.
Outline / Operational / Strategy / Security / Programming
Outline / Operational / Strategy / Security / Programming
Outline / Operational / Strategy / Security / Programming
Outline / Operational / Strategy / Security / Programming
The applicant registration software implements the PEKE responder
procedure. Thus, it expects the initiator message that contains the random
xA->B, where
xA->B<C. The rationale behind the use of an initiator message in the PEKE
cryptosystem is related to number-theoretic attacks and subtle
weaknesses in cryptographic protocols and their implementations. The presence
of the number
xA->B protects the issuer against a number-theoretic attack called
"chosen ciphertext attack", even if the initiator message generation
is not done by the issuer. The issuer may use discipline in the way
initiator messages are generated to ensure absolute uniqueness or
freshness of the secret key generated by instances of the PEKE protocol.
For uniqueness, the issuer should tag each initiator message with a
serial number and make sure any serial number is used only once. For
freshness, the issuer should keep record of creation times for initiator
messages and reject older ones. In practice, immunity to chosen
ciphertext attack is more than academic for PEKE. The other properties may not
be critical in 1997 but might become important as the defrauders get
smarter and smarter.
The applicant registration software needs access to the issuer's parameter to proceed with the local generation of an internal secret key. This is where the Frogbit data integrity algorithm becomes effective: the decryption or data recovery operation should detect any attempt to modify the (concealed) set of issuer's parameters.
The local generation of an internal secret key is the main purpose of
the PEKE responder procedure. This uses the set of issuer's parameters
and the private random source. The result is the internal secret key
w and the component
xt for the
second
message to be sent ot the issuer data processing facilities. If usage is made
of the PEKE modification suggested to fully exploit the
Montgomery method, the component value
xt is replaced by the value
xt'=xt×bn mod N.
Outline / Operational / Strategy / Security / Programming
Outline / Operational / Strategy / Security / Programming
A simple key derivation scheme is adequate to derive other keys from
the internal secret key
w generated by the PEKE cryptosystem. Indeed, the recommended scheme is
to set PEKE parameters
k and
t for to generate internal secret key that is the concatenation of
derived keys. A first derived key is the long term secret identification
key generated by the SAKEM procedure. The long term secret
identification key is the first 112 bits of the 336 bits internal secret key.
In the three-factor security scheme suggested to control access to the identification key by the applicant, a PIN is passed to a hash function. This is a typical application of a hash function.
Outline / Operational / Strategy / Security / Programming
The MAC'ing followed by encryption of the registration request data is a typical application of traditional cryptography. The registration data contains the pass query, the pass reply, and the other application-specific data. This data is sealed with a Message Authentication Code (MAC) using the CBC-MAC construct with the triple-DES block encryption algorithm, and a secret key that is the middle 112 bits of the 336 bits internal secret key. The MAC code is appended to the registration data. Then, the registration data and the MAC code are encrypted with the triple-DES encryption algorithm, the CBC mode of operation, an initialization vector set to zero, and a secret key that is the last 112 bits of the 336 bits internal secret key. The result is the registration data ciphertext.
Outline / Operational / Strategy / Security / Programming
Once the second message is received in the issuer data processing
center, the reversed cryptographic processing may be executed for this
particular second message. As a first step, the issuer software completes
the PEKE intiator procedure. Thus, it expects the value
xt in the second message from the applicant. (If usage is made of the
PEKE modification suggested to fully exploit the
Montgomery method, the value
xt is computed from the value
xt'=xt×bn mod N found in the second message.) This value
xt is associated with a value
xA->B. From the knowledge of the private counterpart
P,
Q, of the public key
N, the issuer computer is able to
xt that would have be sent to the issuer in order to probe its private
key using the chosen ciphertext attack, and
w shared with any computer that considered
xA->B and
N in the computation of
w and
xt.
Outline / Operational / Strategy / Security / Programming
Outline / Operational / Strategy / Security / Programming
Outline / Operational / Strategy / Security / Programming
Outline / Operational / Strategy / Security / Programming
Outline / Operational / Strategy / Security / Programming
[ CONNOTECH home page: http://www.connotech.com/ | SAKEM web page: http://www.connotech.com/sakem.htm | about us | web editorial policy | e-mail to: info@connotech.com ]
CONNOTECH Experts-conseils Inc.
9130 Place de Montgolfier
Montréal, Québec, Canada, H2M 2A1
Tél.: +1-514-385-5691
Fax: +1-514-385-5900