PCP - A Short Description

August 2003

Why the Pure Crypto Project started

As crypto products have developed over the years they have become more and more complex and also more inscrutable leaving the user in a fatal dependence on crypto code which almost nobody fully understands nor analyses for all its security implications. Most people have inevitably accepted this situation without being able to know in detail what they are doing when they use crypto programs, although the basic principles are widely known, the specifications are all published and of course the code is open for inspection. But as the code grows more and more complex it is simply beyond the state of the art to analyse this sort of code with respect to all implications for security.

The Pure Crypto Project (PCP) started to turn the process in a different direction and to tackle the inscrutability problem by developing a program that consists of a very small amount of highly readable code that will be clear and understandable not only for security experts but for many crypto-literate people. So the most important objective of PCP is to restrict itself to one well known basic function (RSA and Modular Exponentiaton) to provide encryption and signing with only a few hundred lines of security relevant code that can be fully analysed with respect to its security implications.

Other Objectives

The Pure Crypto Project will use every RSA key regardless of its origin (PGP, SSH, SSL) with moduli longer than 1000 bits once they are stored as a long number in decimal digits and it will prevent manipulations of keys of any kind reliably and transparent to the user. This is a lecture that should have been learned from the ADK problem. According to the numerous possibilities of attacks against public key cryptosystems known today PCP will ensure long-term security and anonymity of its output - which will be only long numbers - by employing security mechanisms to defeat known attacks which have been successful against other crypto products in the past.

To reduce the security relevant code PCP does deliberately not employ a symmetric cipher but uses RSA for encryption and a discrete logarithm hash function which relies on the basic cryptographic function of Modular Exponentiation used for RSA as well.

Non-Objectives

Most crypto programs use symmetric ciphers to speed up their performance thus saddling themselves with the burden to generate random session keys. Therefore reducing the crypto code will not only mean to avoid a number of different crypto algorithms but would also make the system slow because not only encryption but also hashing is done with Modular Exponentiation, which is expensive with respect to performance. On recent PC computer hardware there is acceptable performance for files of no more than 100 Kbyte but PCP will remain an ineffective means for encrypted storage of big files.

And of course with doing crypto in a different way the compatibility of PCP's output with other popular encryption software is gone. But you simply cannot solve the inscrutability problem and preserve compatibility with all the different algorithms that cause the complexity problem. As PCP restricts itself to the basic encryption and signing process to gain transparency it will not provide a GUI because it is simply not pure crypto nor will it include a key generation process or the means to check certification chains on keys as there are a number of ways to do that reliably. Keys being used by PCP have to be signed by the user to become available and will be protected with a security hash that will be displayed to the user every time a key is being used.

Design-Decisions

To provide some background information on PCP I will now explain some design decisions which have been taken to asure the long-term security of PCP.

PCP provides separate basic functions for signature creation, signature verification, encryption, decryption, hashing and wiping of files. It can be used interactively or within a pipeline.

As soon as an RSA key is longer than a minimum keysize of 1000 bits it can be used in PCP regardless which software product had created the key pair once the essential key material (modulus, encryption and decryption value and a User-ID) is extracted and stored as decimal digits in a file that holds the key. At the moment there are programs coming with PCP to extract RSA keys from PGP-format (both version 3 or 4) from SSH key format and from X509 OpenSSL private key file formats. The extraction software will also calculate the security hash of the essential key material it can be recognized and checked by after publication to others.

A key is a pretty simple structure with no way of extensions to avoid unwanted side-effects, it consists of an RSA modulus (line 1) the public encryption exponent (line2), a hash modulus (line 3), a hash generator (line 4), the user's identification information (line 5) and a security hash (line 6) and nothing else is a valid public key. As the discrete logarithm hash function (SDLH) uses two public parameters (hashmodulus and generator), the user's public keyfile must comprise these key material which is protected by the security hash as well. There is a separate signing key and an encryption key. So the long-term signingkey can be longer than the temporary encryption key currently in use which may be changed more frequently. Every time a key is used the security hash of the key will be displayed to show the integrity of the key in use. This prevents manipulations of keys in PCP to remain concealed.

Trust in the integrity of a person's key file is introduced by the user of PCP alone by signing the keyfile himself. There is no PKI (Public Key Infrastructure) in PCP as there are lots of ways to convince someone, that a given key material is trustworthy. On the other hand the user may be convinced that a public key should no longer be used and renders it unusable by deleting his signature on the keyfile. There is no need for PCP to provide ways to get the evidence of the revocation as there are plenty of different means to do that, but anyway the existence of a valid user's signature on a keyfile is the basic precondition for its use in PCP.

As key material is stored in decimal digits in the clear PCP need not to distinguish between signatures on text and signatures on keys. In any case a signature comprises of the message string (as stored by the OS in the inputfile) a timestamp (as provided by the OS) a user's identification string (as part of the long-term signingkey) and of course the encrypted hash value of the message string, giving enough information to know which key is to be used to verify the signature.

On the other hand an encrypted message will consist of decimal numbers only, nothing else. To decrypt it you have to know the recipient's secret encryption key otherwise you will fail, which would take a while to notice. There is deliberately no symmetric cipher in PCP and the encryption of plaintext is done using modular exponentiation - a function of 10 lines of code - , the core algorithm of RSA. Thus a cryptogram will consist of decimal numbers only, giving no clue which key was used to encrypt it providing anonymity of the recipient who is meant to receive the cryptogram.

With no symmetric cipher on board PCP has to solve the problem of protecting the user's secret keys (signing and encryption) while they are stored on the local system. Because of the fact that the secret keys are protected with a user's passphrase PCP creates a sequence of truely random data (a pad) to mask the secret key with an XOR operation. Provided that the passphrase contains enough entropy and the random data pool really does supply truely random data the pad will not be recoverable without the passphrase. Checking the quality of the random data pool will not be PCP's job, although the security of the secret key will depend fundamentally on this property and of course on the quality of the user's passphrase.

Another crucial element of the Pure Crypto Program is the hash function which ideally will be based on exactly the same foundation as the encryption scheme. In this respect the proposal of a discrete logarithm function (SDLH) once invented by Adi Shamir offers both a clear concept and provable collision resistance. The output of the hash function is limited by the hash modulus, so that output values are at least 1000 bits long. Furthermore the output values will depend on the user's key material rendering birthday attacks and precomputation attacks much harder. Despite the clear advantages of the discret logarithm hash function there is not much practical experience collected by now, a fact which raised concerns that nothing new should be used but the standard hash functions like SHA-1 which are supposed to have been subject to intense scrutiny and review. Consequently PCP was designed to run in two different modes. The "conservative mode", being the default mode, which addressed the concerns of those who will only trust standard algorithms uses SHA-1 as the hash algorithm under all circumstances. Clearly this is a compromise solution because at this point the program relies on a precompiled module implementing SHA-1 breaking with the idea of pure crypto which should entirely be understandable by the user.

But secondly a "pure mode" will use the discrete logarithm hash function SDLH which will be used with moduli longer than 1024 bit, so that the hash values used in signatures will be at least that long. With more scrutiny and experience I am convinced that sooner or later SDLH can be the default mode of PCP, making the "SHA-1 concession code" obsolete in the near future.

This is only a very short description of PCP and I am preparing a more comprehensive analysis
which will explain all the background information on PCP with references to the open source code.
Anyway you will find an analysis of the security issues in PCP on the PCP-Homepage.