CONNOTECH Experts-conseils Inc.

Programming Issues in the SAKEM Procedure

Say "Open, Sesame" to Electronic Identification!

Table of Contents

    Outline / Operational / Strategy / Security / Cryptography

Introduction

"SAKEM" stands for "Secret Authentication Key Establishment Method." It is useful for the issuance of electronic identification devices. This document covers the SAKEM procedure from the programmer's perspective, and the system analyst as well.

The SAKEM procedure uses a public key cryptosystem, namely PEKE ("Probabilistic Encryption Key Exchange"). As with most public key cryptosystems, PEKE computations are made with integer arithmetic, and often with very large operands. The appropriate software optimisation technique known as the Montgomery method is described in an hypertext document entitled "Software Acceleration for Public Key Cryptography".

The symbol "|" represents concatenation of k-bit strings, and tacitly specifies a conversion from integer to bit string. Any of the following symbols should be read as if it was a one-letter symbol: xA->B, xB¦, alpha, beta, µ, and nu.

    Outline / Operational / Strategy / Security / Cryptography

Definitions and context

Issuer

The issuer is the organization that issues secret keys for identification purposes.

    Outline / Operational / Strategy / Security / Cryptography

Applicant

The applicant is the new customer, client, subscriber, or member to whom a secret key will be issued.

    Outline / Operational / Strategy / Security / Cryptography

Identification token

An identification token is a portable memory device, e.g. a smart card, that may be used to store the secret key issued to the applicant.

Obviously, a programmatic interface is needed for the access to the identification token.

    Outline / Operational / Strategy / Security / Cryptography

Reduced cost of highly secure electronic transactions

SAKEM advances the affordability of highly secure electronic transactions.

    Outline / Operational / Strategy / Security / Cryptography

Call centers

Doing business over the telephone is a general trend in service industries.

The SAKEM procedure requires a single on-line interactive computer screen for the task of verifying the applicant's identity. This task is usually assigned to a call center employee who is already equipped with an on-line terminal.

    Outline / Operational / Strategy / Security / Cryptography

Broad distribution of low cost software and electronic devices

SAKEM fits well in the ever-decreasing up-front price charged for software, computers, and other electronic equipment.

    Outline / Operational / Strategy / Security / Cryptography

Preparation steps by the issuer

The issuer gets a private/public key pair for a public key cryptosystem.

Here are a few programming tips for the generation of a PEKE private/public key pair:

• To find prime numbers P2 where 2×P2+1 and 4×P2+1 are also prime numbers, start with numbers P2 of which the last digit, in a given small base (e.g. B=2310=2×3×5×7×11) makes it possible for 2×P2+1 and 4×P2+1 to be prime as well. In other words, make sure none of P2 mod B, 2×P2+1 mod B, and 4×P2+1 mod B are divisors of B. The random source that gives P2 must be very secure.
  
  
• From an acceptable P2 in the above paragraph, apply the [[Miller-Rabin probabilistic primality test]] (theoreticallly speaking, the Miller-Rabin test is a compositeness test, but for practical purposes, it is an excellent test for prime numbers) in parallel for P2, 2×P2+1, and 4×P2+1. In other words, reject P2 as soon as one of P2, 2×P2+1, or 4×P2+1 is found composite. The random source used for the Miller-Rabin test need not be secure.
  
  
• To ensure that "2 is a quadratic residute with respect to" a prime number P for P mod 4=3, compute x=2(P+1)/4 mod P, and then 2 is a quadratic residute with respect to P if and only if x2 mod P=2.

To speed up the the issuer computations, it is useful to pre-compute the integers a and b such that a×P+b×Q=1, and
alpha=((P+1)/4)(t+1) mod (P-1), and
beta=((Q+1)/4)(t+1) mod (Q-1).

Considering all the useful precomputations, the public key is N plus the Montgomery precomputed parameters for N, and the private key is the set of integers P, Q, a, b, alpha, and beta, plus the Montgomery precomputed parameters for P and Q.

    Outline / Operational / Strategy / Security / Cryptography

The issuer prepares an applicant registration software.

The set of issuer's parameters includes the public key N, with the Montgomery precomputed parameters for N. It also includes S, C, k, t, maybe b and n, and the Montgomery precomputed parameters for S. This said set of parameters may also include identification data for the issuer, like the electronic mail address where the secret key registration should be sent.

    Outline / Operational / Strategy / Security / Cryptography

The issuer releases the applicant registration software.

    Outline / Operational / Strategy / Security / Cryptography

Preparation steps by the applicant

The applicant obtains the applicant registration software.

    Outline / Operational / Strategy / Security / Cryptography

The applicant obtains a blank identification token.

    Outline / Operational / Strategy / Security / Cryptography

Computerized portion of the SAKEM procedure

The applicant starts the registration software.

The applicant registration software implements the PEKE responder procedure. Thus, it expects the initiator message that contains the random xA->B (the initiator message generation is the first step of an instance of the PEKE secret key establishment protocol). The initiator message may be generated by the issuer, by the applicant registration software itself, or by another party (e.g. the issuer Internet service provider). If the generation is done by the applicant registration software, there is obviously no transmission of initiator message to the applicant registration software. If the initator message is not generated by the issuer, the issuer must somehow receive its contents.

In any case the applicant registration software includes a reference to, or the contents of, the initiator message in a second message to be sent ot the issuer data processing facilities. If a third party is involved, it should affix reference numbers to initiator messages and keep a log of generated messages. This would allow the issuer to audit the generation of initiator messages.

The private random source should use a pseudo-random generator. Its state should be stored in a computer file. The pseudo-random state should be encrypted when written to the file, and decrypted when read from the file. The encryption algorithm should be a Frogbit semi-proprietary algorithm, preferably different from the one protecting the integrity of the issuer public key. As a source of truly random data, the registration program should require arbitrary user input, and the computer clock should be used as well. This truly random data should be passed to a hash function (e.g. MD5 or SHA), and the result be split in two halves. The two halves should be used to vary the pseudo-random state respectively before and after its use. If the [[Blum Blum & Shub]] generator is used, the state variation may be implemented as the "exclusive or" of the hash half and the low order bits of the generator state. The sequential process is thus:

1. read the encrypted pseudo-random generator state file,
2. decrypt the pseudo-random generator state si,
3. hash the truly random input in two hash parts, h1 and h2,
4. vary the state as in si'=variation(si,h1),
5. use the pseudo-random generator as needed, so its state is updated to si+1,
6. vary the state as in si+1'=variation(si+1,h2),
7. encrypt the pseudo-random generator state si+1',
8. store the encrypted pseudo-random state in the file.

The private random source produces the secret random number xB¦, and the internal secret key is computed from xB¦, xA->B, S, C, N, t, and k. According to the original PEKE specification, the computation equations are:
x=(xB¦-(xB¦ mod S))×C+xA->B×S+(xB¦ mod S),
x0=x2 mod N,
xi+1=xi2 mod N, where i runs from 0 to t-1,
Bi=xi mod 2k, where i runs from 0 to t-1, and
w=B0|B1|...|Bt-1.
If usage is made of the PEKE modification suggested to fully exploit the Montgomery method, the above equations are changed to
x=(xB¦-(xB¦ mod S))×C+xA->B×S+(xB¦ mod S),
x'=MN,B(x,b2n mod N),
x0'=MN,B(x',x'),
xi+1'=MN,B(xi',xi'), where i runs from 0 to t-1, and
Bi=xi' mod 2k, where i runs from 0 to t-1, and
w=B0|B1|...|Bt-1.

    Outline / Operational / Strategy / Security / Cryptography

The applicant chooses and types a pass query and a pass reply.

    Outline / Operational / Strategy / Security / Cryptography

The secret key is loaded in the identification token.

    Outline / Operational / Strategy / Security / Cryptography

The registration program sends a registration request message to the issuer data processing center.

In the programming of the CBC mode of operation, if a random initiation vector is used instead of a fixed one, it is very important that the random source used for the initialization vector be totally unrelated to the private random source. For instance, the computer clock should not be used in both random sources.

1) the ciphertext representation of the encrypted data, 2) the un-encrypted portion, if any, of the other data 108, and 3) the calculated MAC.

In summary, the second message from the applicant to the issuer data processing center contains the following components:

1. a reference to, or the contents of, the PEKE initiator message (xA->B),
   
   
2. the component xt from the PEKE responder procedure (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),
   
   
3. the registration data ciphertext.

    Outline / Operational / Strategy / Security / Cryptography

The issuer data processing center receives the request, processes it and files the application request in the issuer database.

The issuer software completes the PEKE intiator procedure. If usage is made of the PEKE modification suggested to fully exploit the Montgomery method, a preliminary conversion must be done with the equation xt=MN,B(xt',1). Then, the following computation must be done:
µ=(xt mod P)alpha mod P,
nu=(xt mod Q)beta mod Q,
e=(b×Q×µ+a×P×nu) mod N,
f=(b×Q×(P-µ)+a×P×nu) mod N,
g=(b×Q×µ+a×P×(Q-nu)) mod N,
h=(b×Q×(P-µ)+a×P×(Q-nu)) mod N,
and then verify that one of e, f, g, or h satisfies
xA->B×S=(? mod (S×C))-(? mod S).
If none of e, f, g, or h verifies this equality when taking the role of the "?", further processing must be aborted for security reasons. If no security incident is detected, the issuer software recovers the internal secret key w with the following computations, starting from the value e:
x0=e2 mod N,
xi+1=xi2 mod N, where i runs from 0 to t-1,
Bi=xi mod 2k, where i runs from 0 to t-1, and
w=B0|B1|...|Bt-1.
If usage is made of the PEKE modification suggested to fully exploit the Montgomery method, the above equations are changed to
x'=MN,B(e,b2n mod N),
x0'=MN,B(x',x'),
xi+1'=MN,B(xi',xi'), where i runs from 0 to t-1, and
Bi=xi' mod 2k, where i runs from 0 to t-1, and
w=B0|B1|...|Bt-1.

    Outline / Operational / Strategy / Security / Cryptography

Conversational portion of the SAKEM procedure

A voice contact is established between applicant and issuer agent.

    Outline / Operational / Strategy / Security / Cryptography

The applicant and the issuer agent mutually verify the knowledge of pass query/reply by the other person in the conversation.

    Outline / Operational / Strategy / Security / Cryptography

The issuer agent verifies the identity of the applicant.

    Outline / Operational / Strategy / Security / Cryptography

The issuer agent flags the registration as being validated in the issuer database.

    Outline / Operational / Strategy / Security / Cryptography

[ 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