31 October 1999
Source: Hardcopy of 37 pages from Anonymous. Original reportedly obtained
from the National Security Agency by FOIA request.
This document is available Zipped (text and 13 images): http://cryptome.org/capstone.zip (298K).
See related declassified SKIPJACK-KEA specifications.
Redactions shown by xxxxxx or as indicated by number of lines or figures. Overstrikes in original.
Classification symbols: U = Unclassified; S = Secret; TS = Top Secret; Umbra = Codeword, a restricted Top Secret category; NF = No Release to Foreign Nationals; FOUO = For Official Use Only; OADR = Orginating Agency's Determination Required (for declassification).
R21 Informal Technical Report
R21-TECH-30-95
14 August 1995
This Document is Classified TOP SECRET
and is Not Releasable to Foreign Nationals in
its entirety.
Classified by: NSA/CSSM 123-2
Delassify on: Originating Agency's Determination Required
THIS DOCUMENT CONTAINS
CODEWORD INFORMATION
Not Releasable to Foreign Nationals
[Each page with header and marked classified as shown
on this page; hereafter omitted]
CAPSTONE (MYK-80) Specifications
THIS PAGE INTENTIONALLY BLANK
Not Releasable to Foreign Nationals
14 August 1995
R21-TECH-30-95
ABSTRACT
(U) CAPSTONE started as an embodiment of a Law Enforcement SIGINT friendly replacement for the Data Encryption Standard (DES). This requirement would offer greater security than DES while permitting legitimate access to traffic. Given these restraints, the project goals were a commercially viable, single-chip solution offering data integrity, confidentiality, public key based key management and authentication. R21 undertook the development of an algorithm suited for CAPSTONE in support of the aforementioned requirements and goals.
(C) [Eight lines redacted.]
Written by: XXXXXXXX R211
Reviewed by: XXXXXXXX R213
THIS PAGE INTENTIONALLY BLANK
Table of Contents
I. Introduction
II. Algorithms
A. SKIPJACK Modes of Operation Specification
B. SKIPJACK Specification
C. KEA Specification
D. E-Mail Applications of KEA
E. Signature
F. Hash Specification
III. Anti-Reverse Engineering Circuitry and Techniques
A. VROM
B. Random Power Fluctuations
IV. Checkword Generation
A. CV checkword
B. Cover/Wrap Checkword
V. Cover/Uncover and Wrap Functions
VI. Key Escrow Circuitry
VII. Key Variable Storage and Loading
VIII. Randomization and Key Variable Generation
A. MI Generation
B. X, K and R Generation
IX. Synchronization
X. Zeroization
XI. Selected Analysis
A. KEA Analysis and Selection
B. E-Mail Analysis and Applications to a "Drop Box"
XII. Conclusion
XIII. Recommendation
Acronym List
References
THIS PAGE INTENTIONALLY BLANK
14 August 1995
1. (U) Project CAPSTONE has been designed as the Next Generation Data Encryption Standard (DES2) for use by the Federal Government. Project CAPSTONE consists of an Integrated Circuit (IC) incorporating a suite of cryptographic algorithms necessary to provide confidentiality, data integrity and public key management. This IC is known as the CAPSTONE device or simply CAPSTONE.
2. (U) The details of the algorithms used in the CAPSTONE device are classified with the exception of the Digital Signature Standard and its associated appendices. When incorporated into hardware and installed in an approved device, the implementation is unclassified.
3. (C) [Nine lines redacted.]
CAPSTONE IC
(1.0 micron)
[Figure redacted.]
figure 1 "CAPSTONE IC Diagram"
1. (U) The CAPSTONE device incorporates the following CLASSIFIED algorithms:
SKIPJACK Codebook Encryptor/Decryptor
KEA Authenticated Key Exchange
CAPSTONE incorporates the following UNCLASSIFIED algorithms which have been published in Federal Information Processing Standards (FIPS).
DSA The Digital Signature Algorithm
SHA The Secure Hash Algorithm
CAPSTONE also contains all of the necessary randomization features necessary for the secure implementation of the above set of algorithms.
A. SKIPJACK Modes of Operation Specification
1. (U) CAPSTONE uses the SKIPJACK codebook for encryption. SKIPJACK is a 64 bit codebook utilizing an eighty bit cryptovariable. Modes of operation are a subset of the FIPS-81 description of modes of operation for DES. These include the following:
Output Feed-Back (OFB) Modes 64 bit.
Cipher Feed-Back (CFB) Modes 8, 16, 32, and 64 bit.
Codebook 64 bit encrypt/decrypt modes.
Cipher-Driven Codebook (CDC) 64 bit encrypt/decrypt modes.
Note that the OFB and CFB modes of operation have been limited. This was an efficiency/memory trade-off that was made in order to conserve IC memory while providing a reasonable range of encryption rates. The modes are described in the following diagrams:
B. SKIPJACK Specification
1. (U) The MYKOTRONX implementations invoke a byte swap from the chip interface to the diagram description as shown below. The byte permutation for the state space is shown in the Table 1. The byte permutation for the load of cryptovariable are in Table 2. Note that the subscripts match the description. The bits within the bytes remain the same.
Table 1: Data I/O Byte Swap |
|||||||
msb |
lsb |
||||||
| d1 | d2 | d4 | d4 | d5 | d6 | d7 | d8 |
| b8 | b7 | b6 | b5 | b4 | b3 | b2 | b1 |
TAble 2: CV Byte Swaps |
|||||||||
| msb | lsb | ||||||||
| k0 | k1 | k2 | k3 | k4 | k5 | k6 | k7 | k8 | k9 |
| cv9 | cv8 | cv7 | cv6 | cv5 | cv4 | cv3 | cv2 | cv1 | cv0 |
2. (S) U [U added by hand where shown following overstrike;
omitted hereafter] SKIPJACK encrypts 8-byte messages by alternating between
the two rules of motion (A and B) shown below. Since the G-function is a
permutation on 16-bits, it requires two
bytes of input and produces two bytes of output. Therefore, in either rule of motion. a step will be defined to be a two-byte movement. A step of rule A does the following:
a. G permutes b1 and b2 as a word (b1 is the high-order byte and b2 is the low-order byte)b. the new b1 is the xor of the high-order byte of the G output, the high-order byte of the counter, and b7
c. the new b2 is the xor of the low-order byte of the G output, the low-order byte of the counter, and b8
d. all of the bytes b3, b4, b5, b6 shift two places to the right (i.e.. b3 becomes b5, etc.)
e. the new b3 is the high-order byte of the G output
f. the new b4 is the low-order byte of the G output
g. the counter is incremented by one.
Rule B works similarly.
3. (S) U In the equations below. the superscript is the
step number and the h and l subscripts for G and the counter
represent the high and low order bytes of those quantities.
The inverse of rule A is closely related to rule B and the inverse of rule B is closely related to rule A. Nevertheless, for completeness, we give the full decrypt equations below.
We now describe separately the G-permutation, the stepping pattern, and the cryptovariable schedule.
4. (S) U G-permutation: The 16-bit
cryptovariable-dependent G-permutation is built from an 8-bit fix permutation
(called an F table) which is implemented as a 256-byte substitution table.
G requires four F-table substitutions and four bytes of cryptovariable. We
give three characterizations of the function below:
a. mathematically:
b. computer algorithmically:
Function G (high, low, step)(* "high" and "low"' are the high and low order bytes of the word input: step is numbered from 0, i.e., step=counter-l *)high = xor( F( xor( low, cv(4*step+0))), high)
low = xor( F( xor( high, cv(4*step+1))), low)
high = xor( F( xor( low, cv(4*step+2))), high)
low = xor( F( xor( high, cv(4*step+3))), low)
return (high, low)
Function G_inverse (high, low, step)
low = xor( F( xor( high, cv(4*step+3))), low)high = xor( F( xor( low, cv(4*step+2))), high)
low = xor( F( xor( high, cv(4*step+1))), low)
high = xor( F( xor( low, cv(4*step+0))), high)
return (high, low)
c. schematically:
5. (S) [Nine lines redacted.]
6. (S) Cryptovariable schedule: the cryptovariable
is 10 bytes long and used in its natural order. So the schedule subscripts
given in the definition of the G-permutation are to be interpreted mod 10.
7. (S) U SKIPJACK F table is given below [compare to
F-table at
http://jya.com/skipjack-spec.htm
]
F-TABLEa3 d7 09 83 f8 48 f6 f4 b3 21 15 78 99 b1 af f9 e7 2d 4d 8a ce 4c ca 2e 52 95 d9 1e 4e 38 44 28 0a df 02 a0 17 f1 60 68 12 b7 7a c3 e9 fa 3d 53 96 84 6b ba f2 63 9a 19 7c ae e5 f5 f7 16 6a a2 39 b6 7b 0f c1 93 81 1b ee b4 1a ea d0 91 2f b8 55 b9 da 85 3f 41 bf e0 5a 58 80 5f 66 0b d8 90 35 d5 c0 a7 33 06 65 69 45 00 94 56 6d 98 9b 76 97 fc b2 c2 b0 fe db 20 e1 eb d6 e4 dd 47 4a 1d 42 ed 9e 6e 49 3c cd 43 27 d2 07 d4 de c7 67 18 89 cb 30 1f 8d c6 8f aa c8 74 dc c9 5d 5c 31 a4 70 88 61 2c 9f 0d 2b 87 50 82 54 64 26 7d 03 40 34 4b 1c 73 d1 c4 fd 3b cc fb 7f ab e6 3e 5b a5 ad 04 23 9c 14 51 22 f0 29 79 71 7e ff 8c 0e e2 0c ef bc 72 75 6f 37 a1 ec d3 8e 62 8b 86 10 e8 08 77 11 be 92 4f 24 c5 32 36 9d cf f3 a6 bb ac 5e 6c a9 13 57 25 b5 e3 bd a8 3a 01 05 59 2a 46
C. KEA Specification
1. (S-NF) U/FOUO [Six lines redacted.]
2. (S-NF) U KEA operations require exponents of length 160
bits. One exponent used in KEA is a user specific secret component which
can be the same as that used for the DSS. As a matter of practicality, the
use of the same public key certificate (i.e.. the same public key, private
key pair along with the same 1024-bit modulus which has been certified by
a trusted authority) is recommended but not required.
3. (S-NF) U The KEA provides security commensurate with
that provided by SKIPJACK. This is on the order of 280 operations.
4. (U) The IC must have the SKIPJACK. We will denote this function with the following notation.
Eu(x) = the SKIPJACK encryption of message x (64 bits) using cryptovariable u.
5. (S-NF) U The IC must be provided the following data in
order to implement the Key Exchange Algorithm (KEA).
p 1024-bit prime number which defines the field wherep = p1023 p1022 ... p0g 1024-bit base for the exponentiation
g = g1023 g1022 ... g0x 160-bit user secret number
x = x159 x158 ... x0Y 1024-bit public value
Y = gx mod p = y1023 y1022 ... y0r 160-bit random value
r = r159 r158 ... r0pad 160 bit secret padding value
pad = pad159 pad158 ... pad0
= 72f1a87e92824198ab0bf689042ee6577d9834fc hex.
The IC must also have a certificate signed by the Trusted Center which consists of the triple
(Y, sig1 , sig2) where sig1 and sig2 are'the two 160-bit signature numbers.
6. (S-NF) U A description of the KEA process follows. For
two users A and B, the subscripts A and B, are used to denote the 'owner'
of the respective values. IC stands for the Integrated Circuit (i.e., the
CAPSTONE device).
a. A and B exchange the signed packets (Y, sig1 , sig2) to the far terminal. Specifically, we have {(YA, sig1A , sig2A)} going to B and {(YB, sig1B , sig2B)} going to A. In addition. any ID information will be included with these packets and signed by the trusted authority.b. Each device does a signature verification on the received packets to confirm that the value Y is that of a valid user on the network. If the verification fails. the process terminates. If the verification checks, go to step c.
c. Each device exchanges random components. ICA generates a 160-bit random number rA and sends
RA = grA mod p
ICB generates a 160-bit rB and sends
RB = grB mod p
Each of these random components is 1024 bits in length.
d. After receiving the far end random component and public key, each device will check to verify both the received values are of order q (where q divides p-1). ICA will compute and verify
RB not equal to 1 and YB not equal to 1
(RB)q = 1 mod p and (YB)q = 1 mod p
ICB will compute and verify
RA is not equal to 1 and YA is not equal to 1
(RA)q = 1 mod p and (YA)q = 1 mod p
If the verification checks, go to step e. Should the verification fail, stop.
e. ICA will take YB and compute the value tAB. ICB will do the same using the received random component
tAB = (YB)rA mod p = grAxB mod p = (RA)xB mod p = tBA
f. Each device computes
uAB = (YA)rB mod p = gxArB mod p = (RB)xA mod p = uBA
g. Each device checks to make sure that
w = tAB + uAB not equal to 0 mod p
If this check passes, go to step h. Else stop.
h. This result is split into two sections
v1 (w/2(1024 - 80)) mod 280 v2 (w/2(1024 - 160)) mod 280
i. The traffic key k is
D. E-Mail Applications of KEA
(S-NF) U For electronic mail applications where the recipient
does not participate in the formation of the traffic key, the recipient's
contribution to the random exchange is replaced with the public key of the
recipient. For the following, let A be the sender and B be the recipient
of the E-mail message We first begin with the formation of the E-mail message.
1. Sending E-Mail
a. A receives the signed packets (Y, sig1 , sig2) of the far terminal. Specifically, we have {(YB, sig1B , sig2B)} going to A. In addition, any ID information will be included with these packets.b. Device A does a signature verification on the received packet to confirm that the value Y is that of a valid user on the network. If the verification fails, the process terminates. If the verification checks, go to step c.
c. Device A sends the random component. ICA generates a 160-bit random number rA and sends
RA = grA mod p
This random component is 1024 bits in length.
d. ICA will compute and verify.
YB is not equal to 1 and (YB)q = 1 mod p
If the verification checks, go to step e. Should the verification fail, stop.
e. ICA will take YB and compute the value tAB.
tAB = (YB)rA mod p = grAxB mod p
f. ICA computes
uAB = (YA)xA mod p = gxBxA mod p = gxAxB mod p
g. The sender computes
w = tAB + uAB
h. This result is split into two sections
v1 (w/2(1024 - 80)) mod 280 v2 (w/2(1024 - 160)) mod 280
i. The traffic key k is
2. Receiving E-Maila. B receives the signed packets (Y, sig1 , sig2) of the far terminal in the E-mail message. Specifically, we have {(YA, sig1A , sig2A)} going to B. In addition, any ID information will be included with these packets.
b. Device B does a signature verification on the received packet to confirm that the Y value is that of a valid user on the network. If the verification fails, the process terminates. If the verification checks, go to step c.
c. Device B receives the random component that A generated.
RA = grA mod p
This random component is 1024-bits in length.
d. ICB will compute and verify.
RA is not equal to 1 and YA is not equal to 1
(YA)q = 1 mod p and (RA)q = 1 mod p
If the verification checks, go to step e. Should the verification fail, stop.
e. ICB will take RA and compute the value tAB.
tAB = (RA)xB mod p = grAxB mod p
f. ICB computes
uAB = (YA)xB mod p = gxBxA mod p = gxAxB mod p
g. ICB checks to make sure that
w = tAB + uAB is not equal to 0 mod p
h. This result is split into two sections
v1 (w/2(1024 - 80)) mod 280 v2 (w/2(1024 - 160)) mod 280
i. The traffic key k is
E. Signature
1. (U) U/FOUO [Fourteen lines
redacted.]
2. (U) [Eleven lines redacted.]
3. (U) Once a message to be signed becomes available, the steps in computing the actual signature values are as follows. First compute the following 160-bit integer
s2 = k-1 (h + (x) · (s1)) mod q
The values s1 and s2 constitute the signature of the message. The message, s1 and s2 are sent to the recipient where the signature can be verified. These are the values sig1 and sig2 in the KEA sections (s1 = sig1, s2 and sig2).
4. (U) In order to verify a signed message, a recipient must have the following global information:
p The modulus being used by the signer.Y The public key for the user who signed the received message.
To verify the signature the recipient then computes the following:
The recipient then checks to see that v mod q is the same as s1. If they are equal the signature is verified.
F. Hash Specification
1. (U) U/FOUO [Nine lines redacted.]
2. (U) U/FOUO [Five lines redacted.]
3. (U) There are four functions, F = (f1, f2, f3, f4) used in the hash. Which function is used is dependent upon the internal step, t, of the SHA. Each is a mapping from V96 to V32 and is listed below in hexadecimal format.
4. (U) A series of constants, K = (k1, k2, k3, k4), are used in association with each function. These constants are listed below in hexadecimal format.
K = (5A827999, 6ED9EBA1, 8F1BBCDC, CA69C1D6)
5. (U) We define a function sY(X) to be
sY(X) = ((2Y(X) \/ (X/232-Y)) mod 232
If X is stored as a single 32 bit word with the bits arranged in decreasing order of significance from left to right, then this is equivalent to a circular shift of X by Y bit positions to the left.
6. (U) With these definitions, we can consider the diagram of SHA shown below:
SHA is stepped 80 times per message block. The values of A, B, C, D, and E are initialized with the intermediate hash values prior to stepping. After 80 steps, the contents of these registers are used to update the intermediate hash value registers by being added to the previous hash values, mod 232. This process repeats until all message blocks have been processed. The final contents of the intermediate hash value register is output as the hash.
1. (S) [Five lines redacted.]
2. (TSC-NF) [Six lines redacted.]
3. (TSC-NF) [Seven lines redacted.]
A. VROM
1. (S) [Five lines redacted.]
2. (U) VROM is a one-time programmable technology developed by Quicklogic, Inc., which was licensed and improved by VLSI Inc. The original intent of the technology was to prevent non-destructive recovery of the memory cell contents of the VROM. The technology is essentially an "anti-fuse'' technique. Instead of using a voltage which physically opens a gap in metal conductor. a voltage is applied to amorphous silicon which causes the resistance of the silicon to be reduced. The amorphous silicon is sandwiched between two layers of metal. Thus a current channel is opened through the silicon (connecting the two metal layers) without physically altering the medium itself.
3. (S) [Three lines redacted.]
4. (S) [Nine lines redacted for items a, b, c, d, e,
f and g.]
B. Random Power Fluctuations
1. (TSC-NF) [Six lines redacted.]
2. (S) [Four lines redacted.]
A. CV checkword
1. (S) [Three lines redacted.]
B. Covert/Wrap Checkword
1. (S) U/FOUO [Three lines redacted.]
[Seventeen lines redacted.]
2. (S) [Seven lines redacted.]
1. (S-NF) [Seven lines redacted.]
2. (S-NF) [Two lines redacted.]
3. (S-NF) [Eighteen lines redacted.]
4. (S-NF) [Twenty-six lines redacted.]
1. (S U.S./Can Eyes Only) [Eight lines redacted.]
2. (S U.S./Can Eyes Only) [Fifty lines redacted.]
3. (S U.S./Can Eyes Only) [Three lines redacted.]
[Full (horizontal) page redacted.]
1. (S) [Three lines redacted.]
2. (S) [Three lines redacted.]
A.
1. (S-NF) [Forty-five lines redacted.]
B. X, K and R Generation
1. (U) U/FOUO [Seven lines redacted.]
2. (U) The following process describes the software randomization process. It assumes that the device in question possesses enough memory to store the 160 bit user secret terminal unique (X) and the seed value, (seed(Tau)), initially provided by the Local Authority (Central Authority). The device must also possess the capability to increment a 48 bit counter. The process is described below.
a) Read in X, (seed(Tau)) at power-up or beginning of each session.b) If no X, (seed(Tau)) has been read in at power up and a random number is needed, then access the MI generation process 4 times.
(X, (seed(Tau)) = MI(t)//MI(t+l)//MI(t+2)//[MI(t+3)mod 232].
c) Initialize 45 bit counter to count = 1.
d) Is a random number needed? If not, wait. If so, go to step e.
e) Compute RN(t) = SHA(X, (seed(Tau)), count, RANDOM). This value can be used in either step g, h, or i, but cannot be used simultaneously in 2 or more of these steps.
f) Increment counter, count = (count +l ) mod 248. If count = 0, then alarm and to to step a.
g) If signature per message random number, k, is needed then k = RN(t) mod q. Go to step d.
h) If Key Exchange Random Number is needed then r = RN(t) mod q. Go to step d.
i) If new X variable is needed, then X = RN(t) mod q. Go to step d.
Should the host require an additional seed input. it is permissible to increment the seed and repeat this process until a new randomly generated seed is available. (i.e., seed(Tau) = (seed(Tau) + 1) mod 264)
1. (S) [Three lines redacted.]
1. (S) [Three lines redacted.]
1. (S) [Three lines redacted.]
A. KEA Analysis and Selection
1. (TSC-NF) [Twenty lines redacted.]
[Full page and one-half redacted.[
2. (S-NF) [Eighteen lines redacted.]
3. (TSC-NF) [Twenty-three lines redacted.]
4. (TSC-NF) [Two lines redacted.]
5. (TSC-NF) [Five lines redacted.]
6. (S-NF) [Ten lines redacted.]
7. (TSC-NF) [Twenty lines redacted for a, b and c and
following.]
8. (TSC-NF) [Three lines redacted.]
1. (S) [Four lines redacted.] cryptographic boundary.
2. (TSC-NF) [Six lines redacted.]
1. (TSC) [Four lines redacted.]
| ARM6
CDC CFB CK CV CCV DES DMS DSA DSS EPROM FIPS IC ID ISSO IV KEA LAW XXX MI MOD MSP MYK-80 NIST PMSP RAM RAND RISC ROM SHA SJ TK UK VROM |
Acorn RISC Machine 6
Cipher Driven Codebook Cipher Feed Back Cover Key CryptoVariable CryptoVariable Data Encryption Standard Defense Message Service Digital Signature Algorithm Digital Signature Standard Electronic Mail Electronically Programmable Read Only Memory Federal Information Processing Standard Integrated Circuit Identity Information Security Systems Organization Initialization Vector Key Exchange Algorithm Local Authority Workstation XXXXXXXXXXXXXXXXXXXX Message Indicator MODular arithmetic metacell (the exponentiator) Message Security Protocol MYKotronx Mark 80 chip National Institute of Standards and Technology Pre-Message Security Protocol Random Access Memory RANDomizer Reduced Instruction Set Computer Read Only Memory Secure Hash Algorithm SKIPJACK Traffic Key Unique Key Vialink Read Only Memory |
1. ''Secure Hash Standard." FIPS- 180: 1993 May 11: U.S. Department of Commerce, Technology Administration, National Institute of Standards and Technology.
2. "Escrowed Encryption Standard." FIPS PUB 185; 1994 February 9: U.S. Department of Commerce, Technology Administration, National Institute of Standards and Technology.
3. "DES Modes of Operation." FIPS PUB 81: U.S. Department of Commerce, Technology Administration, National Institute of Standards and Technology.
4. "Proposed Federal Information Processing Standard for Digital Signature Standard (DSS)." Federal Register. v.56, n.169: 30 August 1991.
5. "SKIPJACK (U)." R21-TECH-043-92: XXXX
R T/Dir
R2
R2 T/Dir
R21
R211 XXXX
THIS PAGE INTENTIONALLY BLANK
[Blank rear cover]
THIS DOCUMENT CONTAINS
CODEWORD INFORMATION
Not Releasable to Foreign Nationals
Transcription and HTML by Cryptome.
Errata welcomed, send to capstone@cryptome.org
