Bifroest Mr. Tines MacCTC CTCjava Manual Pages
Bifroest Mr. Tines CTC Home CTClib MacCTC CTCjava Manual


 

What has CTC done?

One of the motivations behind the writing of CTC was to extend the number of cryptographic and related algorithms available over the patented ones in the original PGP, in particular to offer an alternative to IDEA, which is a widely patented algorithm, so as to have a commercially useable freeware solution for data protection. Consequently, CTC has had to make changes to the file formats that will enable it to generate PGP-compatible messages with extensions such that PGP will fail gracefully if presented with something that is not vanilla RSA/IDEA/MD5.

This file documents the changes made to the basic formats shown in PGFORMAT.TXT within the 2.6 family of PGP release packages. Currently the PGP5.0 extensions are not fully supported.

New algorithms

All the XXA_TYPE constants referred to below are to be found in file keyconst.h

Public Key Encryption and Digital Signature

In addition to RSA, an elliptic curve encryption algorithm based on elliptic curves on GF(2^255). This is more related to key exchange than true reversible encryption in its operation. The code also recognises the algorithm bytes used by Viacrypt in the commercial version of PGP to restrict a key to pure signature or pure encryption use. It is the job of the user interface to honour the intent of Viacrypt specific values.

Algorithm byte values have bit 7 set if they are CTC extensions; recognised values include

I only hope that the official PGP 5.0 team have been as scrupulous about recognising the Viacrypt extensions - it would be embarassing if 2 also meant El Gamal! (though their use of version byte value 4 should allow the intended cypher to be distinguished).

The EBP2.7 extension of PGP2.6i uses 86 to indicate RSA in conjunction with a non-standard algorithm, and 97 to indicate Rabin. These algorithms are not yet supported in CTClib.

Elliptic curve encryption overview

The elliptic curve algorithm works as follows. A known point P on a suitable elliptic curve is common to all keys. The secret key is a 240 bit random quantity R, and the public key is the value R*P. Encryption is performed by choosing a random value K. The quantity K*P is transmitted, and the value K*public-key = K*R*P is used as the shared random secret. On receiving K*P, the owner multiples K*P by the secret value to get (K*P)*secret-key = K*P*R = K*(public-key), multiplication being commutative.

Note that the value K is lost - recovering it by division is equivalent to breaking the cypher, this being the trapdoor function - so we cannot do as for PGP-classic and say K=data encryption key packet.

It would seem at first glance that we could sign messages by setting K=message digest packet, and sending K*R, so that the receiver generates (K*R)*P and compares it with his own computed message digest packet K' multiplied by the public-key, so as to get K'*(R*P) for comparison. Unfortunately, the multiplication operation is only defined if one if the entities is a point on the curve - neither K nor R are such points, so we cannot form the product K*R.

Instead the Nyberg-Rueppel scheme is used for signatures. The mechanics of the scheme require a little more technical details of the elliptic curve mechanism to be discussed for a full description; but it runs as follows:

A random value K is chosen and the x-coordinate of K*P is added to the value H to be signed. This value is S1. A second value S2 is given by K-(secret-key*S1); all this is done modulo N where N is such that N*P is zero. S1 and S2 together form the signature

The signature is verified by computing whether Q = S1 - x-coordinate of(S2*P + S1*public-key) equals H, mod N. Denoting x(thing) as the operation of taking x coordinates of thing, we see that

S1 = x(K*P) + H

S2 = K - (R*S1) = K - R*x(K*P) - R*H

Q = x(K*P) + H - x(K*P - R*P*x(K*P) - P*R*H + x(K*P)*R*P + H*R*P)

and we see immediately that all the terms inside x() cancel to leave Q = H (mod N). Note that we are in general not guaranteed to exactly recover the value of H (although if H < N, or we can add multiples of N to retrieve a known form, this limitation can be worked around).

Technicalities of the elliptic curve used

The field is represented as polynomials of degree 17 with coefficients which are elements of GF(2^15). In the following, t is used for polynomials in the small field, q is used for the degree 17 polynomials. A reduction trinomial with coefficients in GF(2) is used, viz. t^0.q^0 + t^0.q^3 + t^0.q^17 The primitive polynomial used for multiplying in GF(2^15) is t^0 + t^2 + t^15 The equation of the elliptic curve is y^2 + xy = x^3 + EC_B where EC_B is the polynomial = ( t^0 + t^5 + t^7 ) . q^0

The order of the fixed point P on the curve is a 241 bit prime.

Conventional Secret Key Encryption

Algorithms

Algorithm byte values have bit 7 set if they are CTC extensions, and bit 6 set to indicate multiple encryption; if bit 7 is set, a second byte follows indicating the mode of encryption, direction, and if triple-encryption is to be used. It is possible to compile CTC with NO_IDEA defined to remove IDEA from the executable entirely.

The 40-bit Blowfish option is provided for use with elliptic curve encryption, whose implementation here has only a 16 byte space for conventional keys. This reduced form of encryption can be used in either triple encryption mode, or for a multiple-pass encryption (e.g. forwards/reverse/forwards) of 120-bit strength. It is the responsibility of the user interface to ensure that the total bit strength of the encryption used is high enough - so that, for example, single pass 40-bit Blowfish is not all that's used!

The EBP2.7 extension of PGP2.6i uses 86 to indicate IDEA in conjunction with a non-standard algorithm, and 97 and up to indicate 4 varieties of SAFER .

Other algorithms supported

The following other algorithms are supported The various AES candidates will probably be added in due course.

Modes of operation

If bit 7 is set in the algorithm byte, the next byte follows defining the mode of operation of the cypher

Discussion of modes

The main advantage of CFB mode is that it handles incomplete blocks naturally, whereas CBC and even ECB with cyphertext stealing require shuffling about in the last full block as well as the last incomplete block (ciphertext stealing) to ensure that the ciphertext is no longer than the plaintext, and the value of the plaintext can be unambiguously recovered.

OFB mode in essence turns the block cypher into a stream cypher; this mode handles the end of plaintext gracefully, and also allows the encryption of partial blocks within the ciphering (for example handling the random block+2 bytes preceding the text in a n encrypted data packet, or the block preceding keys.

Both CFB and OFB modes can be used with non-reversible operations (e.g. hashing functions); this adds to their attractiveness.

Currently only CFB mode is permitted for secret key protection, since this allows each MPN within the key to be encrypted separately as a whole, and recovered similarly.

Message Digest

In addition to dedicated hashing algorithms, like MD5, CTC offers a hash based on 3-Way (to produce 96-bit hashes to put into 3-Way) with MD strengthening as per MD5. The procedure used is the first from Table 18.1 of Schneier, H[i] = E<H[i-1]>(M[i]) ^ M[i], following some arbitrary choice of H[0].

Algorithm byte values have bit 7 set if they are CTC extensions.

The EBP2.7 extension of PGP2.6i uses 86 to indicate MD5 in conjunction with a non-standard algorithm, and 97 and up to indicate the 15 varieties of HAVAL (as are the 15 varieties with a correction to the MD strengthening) . These algorithms are in CTClib, as are the RIPEM versions used in PGP 5.0.

Compression

As well as the basic deflate method, an interesting method based on Markov processes in splay trees has been implemented to complete the proof of concept, allowing all labelled algorithms to be chosen, and extensions to be made easy.

Algorithm byte values have bit 7 set if they are CTC extensions.

OpenPGP's use of ZLIB compression is not yet supported.

Itemised changes by section

1.3 KeyID

For the Elliptic Curve algorithm, the 64 bits are extracted from the single MPI that forms the key; similarly this is the only value that can be input to a keyprint.

1.6 Cypher type byte (CTB)

PGP inconsistency:There is a mismatch between documentation and reality in PGP classic, which CTC follows for compatibility : if the type is a key certificate or a signature packet, then the packet length field is always 2 bytes, even if the high byte is thus zero.

1.7 [RSA] public-key-encrypted packet

The document states that after byte 12, the algorithm byte, the subsequent fields are algorithm dependent. If byte 12 takes the value PKA_GF2255, the subsequent fields are as follows 
Offset  Length  Meaning
13      1       number of pairs of MPIs following (should be 1)
14      ?       MPI of intermediate value generated by elliptic
                curve key exchange
?       ?       MPI of XOR of DEK packet and exchanged key.

1.8 Signature packet

The document states that after byte 18, the subsequent fields are algorithm dependent. If byte 18 takes the value PKA_GF2255, the subsequent fields are as follows 
Offset  Length  Meaning
19      1       Algorithm byte for message digest
20      2       First two bytes of message digest 
                (can detect simple minded tampering only)
22      ?       MPI for first part of signature
?       ?       MPI for second part of signature
PGP inconsistency: Note that despite the comment in PGFORMAT in the second paragraph after listing the signature classification fields, to the effect that packet headers are omitted, PGP-classic does actually include these bytes. CTC follows suit for backward compatibility.

1.9 Message Digest packet

Since the general public key system does not perform an invertible encryption, but merely provides a way of getting suitable trapdoor functions, there need be no message digest packet retrievably hidden in the Signature packet. Instead the value resulting from SIGN(digest-packet, secret-key) must in general be fed into a VERIFY along with the public key and what is presumed to be the signed packet.

As PKA_GF2255 only allows a 30 byte space for the signature packet, the ASN is omitted in this case. Otherwise the format is unchanged even though the ASN number ought strictly to be altered to conform with the appropriate RFC, if a suitable value exists for the signature method.

1.10 Conventional data encryption key (DEK) "packet"

The data format for this field for PGP versions 2.2 and earlier use the first non-zero byte, documented as value 1, to hold the IDEA algorithm byte.

The data format for this field in later versions and PGP is as follows 

MSB                                                    LSB
0  2 RND(n bytes) 0 AlgorithmPacket KeyPacket CSUM(2bytes)
where the RND bytes are non-zero random, so that the zero is a "heads-up" to signal the start of the Algorithm "packet", which has structure 
Offset  Length  Meaning
0       1       Algorithm - if CEA_IDEA, this is the end of the packet
1       1       Mode byte
2       1       Next algorithm (if previous one had CEA_MORE_FLAG set)
3       1       Mode byte
etc. until mode after Algorithm without the CEA_MORE_FLAG.
and the Key "packet" supplies enough bytes for the above-specified algorithms in order, with, if CEM_TRIPLE_FLAG is set, three times the single key length being dedicated to the algorithm.

1.11 Conventional key encrypted data packet

The 64 bits of random value in classic PGP are the IV for the CFB mode. The presence and size of such will depend on the mode and algorithm used respectively.

1.12 Compressed data packet

There is no change apart from the value of byte 1 to CPA_SPLAY for the splay tree case - this algorithm also knows when to stop (when it decompresses an out-of-band byte value (256 as opposed to byte values of 0-255, for the curious), and will merely finish consuming the current byte before exiting.

1.14 Comment packet

CTC does not generate these. It *ought* to display them, depending on the UIF, as the contents are passed up from the engine, should such a packet be found. Precautions are taken to ensure that comment packets with embedded nulls can be detected - this packet type would otherwise be wonderfully suited to being a subliminal channel for all sorts of nasties.

1.15 Secret key certificate

Fields are, as expected, indeed dependent on the algorithm byte at offset 10. For a GF(2^255) public key system, a single MPI suffices for each of the public and private keys, rather than 2 and 4 respectively for RSA in all variations.

In any case, the key protection conventional cypher algorithm identification byte may have the CEA_FLEX_FLAG set; if so a mode byte follows to fully define the cypher. In addition, if the algorithm byte has CEA_MORE_FLAG set, then a second byte follows to indicate the hashing scheme used to turn the passphrase into a key. If there is a mismatch between hash and key sizes, then the output of the hash repeats if the key is longer; otherwise only the first key-length bits are used from the hash.

The IV size and presence depends on the encryption algorithm and mode.

1.16 Public key certificate

The changes to this packet are a subset of those for the Secret key certificate. The algorithm byte at offset 10 controls how many MPIs are needed to define a public key.


webmaster@bifroest.demon.co.uk