Questions about future and session key generation in DUKPT process

As I understand this process is done in the client device for generating a unique key per transaction:

1. inject generated IPEK to client device;
2. generate set of future keys (actually 21 future keys) using IPEK+KSN and delete the IPEK;
3. generate session key using transaction key + KSN;
4. use this session key per transaction and for next transaction use increment KSN and use next future key.

My questions:

1. Why we need session key? While future key itself is a unique key and if we encrypt each transaction by a future key, actually we used a unique key per transaction.

2. Why we generate only 21 future key? Then after 21 transaction we need new future key and because of deleting IPEK, then we need to inject a new IPEK to device and as I know, from security point of view this is not good idea to transmit device master key in short cycle like every 21 transaction. Why do we not use a bigger cycle like thousands?

3. How we transmit new IPEK to device after 21 transaction? there are no description about this? Does IPEK encrypted with any other key and then send to device or it sent plain? EDIT:

session key is coming from here :

The swiper usually encrypts these tracks using one of its generated future keys (called the "Session Key") along with its current KSN.

Assume this situation:

1. IPEK is injected to device and 21 future keys are generated
2. first future key + KSN is used to encrypt 1th transaction and KSN was increased
3. do this until using 21th future key for 21th transaction.

4. know for 22th transaction do we used 1th future key + increased KSN or new future keys are used ? If first state then does this means 1th encryption key and 22th encryption key are only differs in KSN ?

EDIT2: dave_thompson_085 describe sequence of generation and using of future keys(thank about it ),the only section which is still unclear to me is detail of generating future keys.I mean assume we want to generate 21 future keys in initial steps,of course we derive this keys from IPEK by 3DES?but do we use IPEK as message and KSN as key for all 21 step future key generation?and after that e.g. for 3th transaction ,when we want to generate and store key in FK21 do we use 3DES encryption with IPEK and KSN for generating FK21?

I don't know where you're seeing session keys. DUKPT is designed to do transactions, not sessions, hence the name. If some application is using them for sessions that is probably a bad idea. (added for edit) Okay, that website is amazing: I think every sentence of the text has an error or ambiguity, yet the code is correct -- at least for the simpler 'host' algorithm; it doesn't implement the device-side future-key algorithm. DUKPT is not intended to and should not be used for session keys.

For the device-side algorithm, the 21 so-called Future Keys are used in a hierarchical fashion controlled by a 21-bit counter (which is the low bits of the KSN) to derive a sequence of keys; they are not directly used as the key sequence. Because high Hamming weights are skipped, the key sequence for a device (starting from an Initial KSN and corresponding Initial Device or TRSM Key, Device or TRSM Injection Key, or various other names) is $2^{20}-1$ or 1048575 keys -- slightly over a million.

(expanded in detail since I can't seem to convey that the 21 future key registers are not 'used up' by 21 transactions; revised to more accurate 'derive' instead of 'generate')

AN EXAMPLE OF THE FUTURE-KEY ALGORITHM

In either host or device (future-key) mode the Initial Key (two 64-bit halves) for a device is created by twokey-3DES encrypting the high 8 bytes of the device's IKSN with the BDK for the left, and with the BDK with each half XORed with C0C0C0C0_00000000 hex for the right.

At device injection this Initial Key is used to derive the keys for each KSN whose counter value is a power of two, and store them in the future-key registers: the key for IKSN+$2^0$=IKSN+1 in FK21, for IKSN+$2^1$=IKSN+2 in FK20, for IKSN+$2^2$=IKSN+4 in FK19 and so on to IKSN+$2^{20}$=IKSN+1048576 in FK1. Since all keys derived by a device are for KSNs beginning with the device's IKSN, I will omit that part from now on and just say the counter value.

For transaction 1, the device (TRSM) finds the lowest 'on' bit in the counter which is $2^0$=1 and uses the key in the corresponding FK register (FK21) which was set above to contain the key for counter 1. Actually the key is first modified to a 'variant' key with two octets complemented depending on the type of crypto done in the transaction. After use FK21 is logically erased.

For transaction 2, the lowest 'on' bit is $2^1$=2 so it uses FK20 similarly and erases it, but first uses it to derive the key for counter 3 and store that in FK21.

For transaction 3, the lowest 'on' bit is $2^0$=1 so it uses FK21 similarly which now contains the key for counter 3 as set above, and erases it.

For transaction 4, the lowest 'on' bit is $2^2=4$ so it uses FK19 which contains the key for counter 4, and erases it but first derives the keys for counter 4+2^1=6 in FK20 and 4+2^0=5 in FK21.

For transaction 5, the lowest 'on' bit is $2^0=1$ so it uses FK21 which contains the key for counter 5 as above, and erases it.

For transaction 6, the lowest 'on' bit is $2^1=2$ so it uses FK20 which contains the key for counter 6 as above, and erases it after generating the key for counter 7 in FK21.

For transaction 7, the lowest 'on' bit is $2^0=1$ so it uses FK21 which contains the key for counter 7 as above, and erases it.

Txn 8 bit $2^3$ uses key 8 from FK18 and derives key 12 in FK19, 10 in FK20 and 9 in FK21.

Txn 9 bit $2^0$ uses key 9 from FK21.

Txn 10 bit $2^1$ uses key 10 from FK20 and derives key 11 in FK21.

Txn 11 bit $2^0$ uses key 11 from FK21.

Txn 12 bit $2^2$ uses key 12 from FK19 and derives key 14 in FK20 and 13 in FK21.

Txn 13 bit $2^0$ uses key 13 from FK21.

Txn 14 bit $2^1$ uses key 14 from FK20 and derives key 15 in FK21.

Txn 15 bit $2^0$ uses key 15 from FK21.

Txn 16 bit $2^4$ uses key 16 from FK17 and derives key 24 in FK18, 20 in FK19, 18 in FK20, 17 in FK21.

Txn 17 bit $2^0$ uses key 17 from FK21.

Txn 18 bit $2^1$ uses key 18 from FK20 and derives key 19 in FK21.

Txn 19 bit $2^0$ uses key 19 from FK21.

Txn 20 bit $2^2$ uses key 20 from FK19 and derives key 22 in FK20 and 19 in FK21.

Txn 21 bit $2^0$ uses key 21 from FK21.

Txn 22 bit $2^1$ uses key 22 from FK20 and derives key 23 in FK21.

Txn 23 bit $2^0$ uses key 23 from FK21.

Txn 24 bit $2^3$ uses key 24 from FK18 and derives key 28 in FK19, 26 in FK20, 25 in FK21.

Txn 25 bit $2^0$ uses key 25 from FK21.

Txn 26 bit $2^1$ uses key 26 from FK20 and derives key 27 in FK21.

Txn 27 bit $2^0$ uses key 27 from FK21.

Txn 28 bit $2^2$ uses key 28 from FK19 and derives key 30 in FK20 and 29 in FK21.

Txn 29 bit $2^0$ uses key 29 from FK21.

Txn 30 bit $2^1$ uses key 30 from FK20 and derives key 31 in FK21.

Txn 31 bit $2^0$ uses key 31 from FK21.

We have now generated 31 transaction keys and have not come anywhere near 'using up' the future key registers -- in fact we've only used five of them, not even touching FK1-16 at all.

If you continue this process for a long time you will see it derives a key for every 21-bit binary value other than zero, of which there are 2097151; but DUKPT prescribes that counter values with more than 10 bits set are skipped, so only 1048575 of these values, and their corresponding keys, are used -- and as I said in the summary above, that's the number of keys and transactions for one DUKPT device, without rekeying.

The original intent was that a device, or (much more likely in the technology of the 1980s and 1990s) the secure module within a device, would be replaced after this cycle. In recent years as DUKPT has been applied to higher-volume but lower-value and lower-security applications, there is more desire for rekeying. See What is transaction capacity of a POS using 3DES DUKPT? for some (differing) perspectives on this.

(further expanded for completeness although this part is correct at the link)

Each derivation step occurs between the key for one KSN and a subsequent KSN which has exactly one bit set that was cleared before, i.e. adds a power of two. For the (trusted) host algorithm, all these steps are performed in a loop, from the highest-order bit set in the desired counter to the lowest-order; for the future-key algorithm they are spread out in time with each bit effectively done at the beginning of the range of counter values which have that bit set, as laid out above; either way the cumulative result for each key actually used is the same.

Each one-bit derivation step uses two single-DES encryptions (but not triple-DES) and is expressed by the standard in a rather complicated form that boils down to:

Input: curkey = key for 'before' KSN, with Left and Right halves accessible separately;
ksn = low 8 bytes of updated KSN (with new bit added) corresponding to new key

Temporary: modkey = curkey with each half XORed with C0C0C0C0_00000000

Output: newkey = key for updated KSN, similarly with Left and Right halves

newkeyR = DES_encrypt(key=curkeyL, data= ksn XOR curkeyR) XOR curkeyR

newkeyL = DES_encrypt(key=modkeyL, data= ksn XOR modkeyR) XOR modkeyR

The website you linked expresses this more concisely in pseudocode as

GenerateKey(key, ksn) { # where ksn is already updated by the caller, and the return is used to update key
return EncryptRegister(key ^ KeyMask, ksn) << 64
| EncryptRegister(key, ksn)
}
EncryptRegister(key, reg) {
return (key & FFFFFFFFFFFFFFFF) ^ DesEncrypt((key & FFFFFFFFFFFFFFFF0000000000000000) >> 64,
key & FFFFFFFFFFFFFFFF ^ reg)
}


The main benefit of the future-key algorithm is that if a device is compromised, the data currently in the FK registers cannot be used to construct any previous keys for the same device, or any keys at all for another device. Thus assuming the compromise is detected and all new keys from this device are blacklisted, the compromise results in no loss of security. DUKPT was originally intended for use in bank ATMs and it was expected (correctly) that some ATMs would be stolen or attacked because, as Willie Sutton famously observed, that's where the money is. The simpler host-side algorithm is capable of creating the key for every txn for every device on demand, but was assumed to be implemented only in a well protected environment, typically a dual-locked vault inside a fortified data center with reinforced walls, fences, and round-the-clock armed guards. And possibly, though an ABA committee would never say so, sharks with frickin lasers :}

• thanks for answering me,I edited my question,can you please give me an brief example of key managements cycle ? – Mahmoud Hosseinipour Nov 25 '17 at 7:32
• @MHD: (greatly) expanded explanation of future-key. I don't know what you mean by 'key managements cycle'; if it's something else, please ask more specifically and clearly. – dave_thompson_085 Nov 27 '17 at 23:18
• really thanks for great answer,then please let me to read your answers carefully many time and ask if there are any question or accept it, with best regards. – Mahmoud Hosseinipour Nov 28 '17 at 9:14
• Thank you a lot, based on your guides on got idea behind 21 set future keys,but still I'm in doubt about generating these future keys,I edited my question for increasing detail, and I will be appreciate for more guide. – Mahmoud Hosseinipour Dec 2 '17 at 5:46
• @MHD: the one-bit-derivation step is correct at the website, but since it's better Stack practice to be selfcontained and I'd already written out the rest I added it, plus an additional note. – dave_thompson_085 Dec 3 '17 at 2:37