Ada Cryptographic Objects

The package ACO (SPARK Ada) is the top level package of this library. It primarly serves as a container for various child packages, but it also holds certain utility types that are of interest to the entire library (and also clients of this library).

The child packages are as follows.

Package ACO.Crypto contains the core cryptographic algorithms.

Package ACO.Access_Types contains the definitions of various useful Access types. These type definitions are not in package ACO because package ACO must be written in SPARK Ada, and SPARK does not allow access types.

Package ACO.Utility contains child packages supporting various utiliity types and subprograms. These are facilities that might in principle be useful outside of ACO but are being provided with ACO as a convenience.

In addition there are private child packages for each raw data type. This is described in more detail below.

Additional child packages of ACO will be defined in the future to provide other cryptographic services (OpenPGP, SSL, etc). At this time no other child packages are defined, however.

The utility types are intended to represent raw, uninterpreted data in various sizes along with the corresponding array types.

    type Octet           is mod 2**8;
    type Double_Octet    is mod 2**16;
    type Quadruple_Octet is mod 2**32;
    type Octuple_Octet   is mod 2**64;
    
    -- Force the raw types to have certain sizes.
    for Octet'Size           use 8;
    for Double_Octet'Size    use 16;
    for Quadruple_Octet'Size use 32;
    for Octuple_Octet'Size   use 64
    
    type Octet_Array is array(Natural range <>) of Octet;
    -- And similarly for the other types.
  

The raw data types are modular types so that they will have intrinsic bitwise operations. Representation clauses are used to ensure that the raw types have the expected sizes. Note that ACO uses the type Natural uniformly for counting.

In addition to intrinsic bitwise operations, it is highly desirable for performance reasons to also have intrinsic bit shift and rotate operations defined for the raw data types. This can be accomplished with GNAT by using a pragma Import directive. However, GNAT requires that the functions specified as intrinsic conform to a particular profile and have particular names. Since SPARK does not allow names to be overloaded and since we wanted to provide instrinsic bit shifts and rotates for all of the raw data types defined in package ACO, it was necessary to create a separate child package for each type (written in SPARK Ada). These packages contain raw data operations of interest to the rest of the ACO library and have names such as ACO.Octet_Operations, etc.

The summary of each of these operations packages is as follows.

    function Shift_Left(Value : Octet; Count : Natural) return Octet
    -- And similarly for the other types in their separate packages.
    
    function Shift_Right(Value : Octet; Count : Natural) return Octet;
    -- And similarly for the other types in their separate packages.
    
    function Rotate_Left(Value : Octet; Count : Natural) return Octet;
    -- And similarly for the other types in their separate packages.
    
    function Rotate_Right(Value : Octet; Count : Natural) return Octet;
    -- And similarly for the other types in their separate packages.

    procedure Xor_Array
      (Accumulator  : in out Octet_Array;
       Incoming     : in     Octet_Array;
       Success_Flag : out    Boolean);
    -- And similarly for the other types in their separate packages.
  

The procedures such as Xor_Array extend the bitwise operations of the raw data types to entire arrays of those types. If the given arrays have different sizes, the value False is written into the Success_Flag parameter and no other operation takes place; otherwise the value True is returned. This approach for handling errors is due to SPARK's restriction against exceptions.

In the future additional raw data operations may be added to the operations packages (whole array shifts and rotates?) The precise operations that will be added will depend on the needs that arise as ACO develops.

The package ACO.Access_Types (full Ada) contains useful access type definitions that can't be put in package ACO because of SPARK restrictions.

    type Octet_Array_Access is access Octet_Array;
    procedure Free_Octet_Array is new
       Ada.Unchecked_Deallocation(Octet_Array, Octet_Array_Access);
    
    type Double_Octet_Array_Access is access Double_Octet_Array;
    procedure Free_Double_Octet_Array is new
       Ada.Unchecked_Deallocation(Double_Octet_Array, Double_Octet_Array_Access);
    
    type Quadruple_Octet_Array_Access is access Quadruple_Octet_Array;
    procedure Free_Quadruple_Octet_Array is new
       Ada.Unchecked_Deallocation(Quadruple_Octet_Array, Quadruple_Octet_Array_Access);
    
    type Octuple_Octet_Array_Access is access Octuple_Octet_Array;
    procedure Free_Octuple_Octet_Array is new
       Ada.Unchecked_Deallocation(Octuple_Octet_Array, Octuple_Octet_Array_Access);
  

Note that only access types for the raw array types are provided. Note also that a suitable deallocation procedure for each array type is also provided.

The package ACO.Crypto (SPARK Ada) contains all the low level cryptographic algorithms in this libary. These algorithms are categorized by various child packages as described elsewhere in this document. The package ACO.Crypto itself contains a few general purpose helper types that are useful to several different child packages.

    type Cipher_Mode is (Encrypt_Mode, Decrypt_Mode, Neither_Mode);
  

The type Cipher_Mode is used by the various cipher objects to track if they are encrypting or decrypting their input data. Most cipher objects start in a neutral state (Neither_Mode) but are then committed to encryption or decyrption after they are initialized (or in some cases after they are first used). Once an object has been committed to a particular mode, it can not usually be switched to a different mode. See the detailed documentation for the child packages of ACO.Crypto for specific exceptions to this rule.

The package ACO.Crypto.Algorithms (SPARK Ada) contains child packages implementing the various core algorithms offered by ACO. These algorithms are used by the object oriented wrappers, but they can also be used directly in programs that don't need the wrappers, or that want to limit themselves to SPARK Ada or Ada 95.

      type Blowfish_Algorithm is private;
      
      procedure Initialize
        (B       : out Blowfish_Algorithm;
         Key     : in  ACO.Octet_Array;
         Success : out Boolean);
      
      procedure Encrypt
        (B       : in     Blowfish_Algorithm;
         Block   : in out ACO.Octet_Array;
         Success : in out Boolean);
      
      procedure Decrypt
        (B       : in     Blowfish_Algorithm;
         Block   : in out ACO.Octet_Array;
         Success : in out Boolean);
    

The package ACO.Crypto.Exceptions (full Ada) contains all the exceptions and related subprograms used by the object oriented cryptographic wrappers.

    Bad_Cipher_Mode : exception;
    Bad_Block_Size  : exception;
  

The exception Bad_Cipher_Mode is raised if one tries to use a cipher object inconsistently. For example attempting to decrypt data after the object has already been committed to encryption mode. Also Bad_Cipher_Mode is raised if the object is used uninitialized.

The exception Bad_Block_Size is raised if a block of the wrong size is given to a Block_Cipher for encryption or decryption.

The package ACO.Crypto.Block_Cipher (full Ada) contains the definition of a root Block_Cipher type along with its associated primitive operations.

    type Block_Cipher is abstract new Ada.Finalization.Controlled with private;
    type Block_Cipher_Access is access all Block_Cipher'Class;
    
    function Block_Size(B : Block_Cipher) return Natural is abstract;
    
    -- In-place form.
    procedure Encrypt(B : in out Block_Cipher; Block : in out Octet_Array);
    procedure Decrypt(B : in out Block_Cipher; Block : in out Octet_Array);
    
    -- Copying form.
    procedure Encrypt
       (B            : in out Block_Cipher;
        Input_Block  : in     Octet_Array;
        Output_Block : out    Octet_Array);
    
    procedure Decrypt
       (B            : in out Block_Cipher;
        Input_Block  : in     Octet_Array;
        Output_Block : out    Octet_Array);
  

The main Block_Cipher type specifies the protocol that must be used with block cipher objects. This protocol is quite simple: to encrypt a block one of the Encrypt procedures must be used, and to decrypt a block one of the Decrypt procedures must be used. Each type derived from Block_Ciper provides its own initialization procedure, if necessary.

There are in-place and copying forms of the encryption and decryption procedures. The in-place form performs its operation on the block in place, overwriting the input block with the result. The copying form writes its result to a new block and treats its input as read-only. Both forms are provided for all Block_Cipher types so that whichever form is more convenient can be used.

In the Block_Cipher type the in-place forms are implemented in terms of the copying forms and visa-versa. Thus derived types need only override one of the forms and can inherit the other form as necessary. Since different ciphers may be more naturally implemented as in-place or as copying, this approach allows the author of a derived type the flexibility of implementing whichever form is most natural for that type. Note that using an "unnatural" form will most likely cause extra copying to be done. Thus for maximum efficiency the developer will want to know which approach is best for the particular ciphers being used. However, all ciphers will provide both forms (perhaps by way of inheritance) so that correct programs can be written either way.

In the copying forms if the output buffer is a different size than the input buffer, the Constraint_Error exception is raised.

Normally a given Block_Cipher instance can be in either encryption mode or decryption mode. The Block_Cipher interface does not specify how this mode is selected. It may be part of the instance's initialization or it may be automatic with the first operation applied to the instance defining its mode. In general Block_Cipher instances can not change mode during their lifetime, although some derived types may provide a way to reinitialize the instance into a different mode. However, some Block_Cipher types may be modeless and can be switched between encryption mode and decryption mode freely. In any case, if an attempt is made to use the wrong mode, for example by calling Decrypt on an instance in encryption mode, the ACO.Crypto.Bad_Cipher_Mode exception is raised.

Function Block_Size returns the size of the block in bits.

    type CBC_Mode is new Block_Cipher with private;
    
    not overriding
    procedure Make
       (B          : out CBC_Mode;
        Underlying : in  Block_Cipher_Access;
        IV         : in  Octet_Array);
  

The type CBC_Mode is a wrapper around Block_Cipher that implements the cyclic block chaining (CBC) encryption mode. It provides the protocol of a Block_Cipher and is initialized with procedure Make. The initialization takes an access value that references an underlying Block_Cipher instance and an initialization vector with a size equal to the underlying cipher's block size (else Bad_Block_Size is raised). Once initialized a CBC_Mode object can be used like any other Block_Cipher. However, be aware that CBC mode retains information about past encryptions so the order in which blocks are processed by a CBC_Mode instance is significant.

Note that when a CBC_Mode instance is finalized the underlying Block_Cipher instance is not modified. Only the additional resources required for the CBC mode implementation are released.

      type Null_Cipher is new Block_Cipher with private;

      not overriding
      procedure Make(B : out Null_Cipher; Block_Size : in Natural);
    

      Bad_Key_Length : exception;
      
      type Blowfish_Cipher is new Block_Cipher with private;
      
      not overriding
      procedure Make(B : out Blowfish_Cipher; Key : in Octet_Array);
    

The package ACO.Crypto.Stream_Cipher contains the definition of a root Stream_Cipher type along with its associated primitive operations. ACO.Crypo.Stream_Cipher also declares types supporting various stream cipher encryption modes.

    type Stream_Cipher is abstract new Ada.Finalization.Controlled with private;
    type Stream_Cipher_Access is access all Stream_Cipher'Class;
    
    -- In-place form.
    procedure Encrypt(S : in out Stream_Cipher; Data : in out Octet);
    procedure Decrypt(S : in out Stream_Cipher; Data : in out Octet);
    
    -- Copying form.
    procedure Encrypt(S : in out Stream_Cipher; Input_Data : in Octet; Output_Data : out Octet);
    procedure Decrypt(S : in out Stream_Cipher; Input_Data : in Octet; Output_Data : out Octet);
  

The main Stream_Cipher type specifies the protocol that must be used with stream cipher objects. This protocol is quite simple: to encrypt an octet one of the Encrypt procedures must be used, and to decrypt an octet one of the Decrypt procedures must be used. Each type derived from Stream_Ciper provides its own initialization procedure, if necessary.

There are in-place and copying forms of the encryption and decryption procedures. The in-place form performs its operation on the octet in place, overwriting the input octet with the result. The copying form writes its result to a new octet and treats its input as read-only. Both forms are provided for all Stream_Cipher types so that whichever form is more convenient can be used.

In the Stream_Cipher type the in-place forms are implemented in terms of the copying forms and visa-versa. Thus derived types need only override one of the forms and can inherit the other form as necessary. Since different ciphers may be more naturally implemented as in-place or as copying, this approach allows the author of a derived type the flexibility of implementing whichever form is most natural for that type. Note that using an "unnatural" form will most likely cause extra copying to be done. Thus for maximum efficiency the developer will want to know which approach is best for the particular ciphers being used. However, all ciphers will provide both forms (perhaps by way of inheritance) so that correct programs can be written either way.

Normally a given Stream_Cipher instance can be in either encryption mode or decryption mode. The Stream_Cipher interface does not specify how this mode is selected. It may be part of the instance's initialization or it may be automatic with the first operation applied to the instance defining its mode. In general Stream_Cipher instances can not change mode during their lifetime, although some derived types may provide a way to reinitialize the instance into a different mode. However, some Stream_Cipher types may be modeless and can be switched between encryption mode and decryption mode freely. In any case, if an attempt is made to use the wrong mode, for example by calling Decrypt on an instance in encryption mode, the ACO.Crypto.Bad_Cipher_Mode exception is raised.

    type CFB_Mode is new Stream_Cipher with private;
    
    not overridding
    procedure Make
       (S          : out CFB_Mode;
        Underlying : in  Block_Cipher_Access;
        IV         : in  Octet_Array);
  

The type CFB_Mode is a wrapper around Stream_Cipher that implements the cipher feedback (CFB) encryption mode. It provides the protocol of a Stream_Cipher and is initialized with procedure Make. The initialization takes an access value that references an underlying Block_Cipher instance and an initialization vector with a size equal to the underlying cipher's block size (else ACO.Crypto.Block_Cipher.Bad_Block_Size is raised). Once initialized a CFB_Mode object can be used like any other Stream_Cipher.

Note that when a CFB_Mode instance is finalized the underlying Block_Cipher instance is not modified. Only the additional resources required for the CFB mode implementation are released.

      type Null_Cipher is new Stream_Cipher with private;
    

The package ACO.Crypto.Hash contains the definition of a root Hasher interface along with its associated primitive operations. ACO.Crypo.Hash also declares a private type to represent the hash values themselves in an abstract way.

    type Hash_Value(<>) is private;   
    function To_String(Value : Hash_Value) return String;
  

The type Hash_Value is an abstract representation of a hash value. It can represent hash values of any length. The function To_String converts hash values into a displayable form. The resulting string is in hex using upper case letters 'A' through 'F'. It also has an appropriate number of leading zeros, depending on the size of the hash value itself. The string does not contain a prefix of "16#" nor a "#" suffix. That is, the string is not in the form of an Ada hex literal. This allows the application to add (or not) any prefix and/or suffix the application deems appropriate.

    type Hasher is interface;
    
    procedure Start_Hashing(Hash_Object : in out Hasher) is null;
    procedure Compute_Hash
       (Hash_Object : in out Hasher; Data_Block  : in Octet_Array) is abstract;
    procedure Finish_Hashing(Hash_Object : in out Hasher) is null;
    function Retrieve_Hash(Hash_Object : Hasher) return Hash_Value is abstract;
  

The main Hasher interface specifies the protocol that must be used with hasher objects. Before any hashing is attempted the procedure Start_Hashing must be called. This procedure initializes the hasher object. It can also be used to re-initialize an object that has been previously initialized.

Procedure Compute_Hash updates the hash value using the raw octets provided in Data_Block. It is not necessary for the given data block to be any specific size. In particular it need not be the natural block size of the underlying hash function. The hasher object will buffer octets if necessary to handle partial blocks.

When all the data has been processed the procedure Finish_Hashing is called to finalize the hash value. After Finish_Hashing has been called, no further calls to Compute_Hash are allowed.

The actual hash value is obtained by calling function Retrieve_Hash. This function can only be called after Finish_Hashing has been called. However, Retrieve_Hash can be called multiple times. In effect, the hasher object is read-only once Finish_Hashing has been called on it.

    Read_Hash : exception;
    
    type Stream_Hasher(Engine : access Hasher'Class) is
       abstract new Ada.Streams.Root_Stream_Type with private;
    procedure Start_Hashing(Hash_Object : in out Stream_Hasher);
    procedure Finish_Hashing(Hash_Object : in out Stream_Hasher);
    function Retrieve_Hash(Hash_Object : Stream_Hasher) return Hash_Value;
    
    overriding procedure Read
       (Hash_Object : in out Stream_Hasher;
        Item        : out Ada.Streams.Stream_Element_Array;
        Last        : out Ada.Streams.Stream_Element_Offset);
    
    overriding procedure Write
       (Hash_Object : in out Stream_Hasher;
        Item        : in Ada.Streams.Stream_Element_Array);
  

In addition to the raw data hasher interface presented above, package ACO.Crypt.Hash defines a Stream_Hasher type. Instances of this type wrap an underlying hasher object and provide a streams interface to the hashing process. The subprograms Start_Hashing, Finish_Hashing, and Retrieve_Hash behave as described above. However, Stream_Hashers are derived from the Root_Stream_Type and thus can be used with 'Read and 'Write attributes in the usual way. To accomplish this Stream_Hasher provides overridings of the Read and Write procedures as apppropriate. The Read overriding simply raises Read_Hash because it does not make sense to read a hasher object as a stream. The Write overriding, however, simply gathers the Stream_Elements and passes them to the underlying hasher for handling.

The intent of Stream_Hasher is to allow one to compute the hash value of an in-memory data structure in a meaningful way. For example, if a complex structure such as a tree is endowed with suitable streaming capability, it can be streamed into a Stream_Hasher to compute its hash value. If the tree is then reconstructed elsewhere (perhaps inside a different program), the hash value can be checked after reconstruction without concerns about "trivial" differences in the external representation of the structure.

      type Null_Hasher is new ACO.Crypto.Hash.Hasher with private;
    

type    Very_Long is private;
subtype Bit       is Natural range 0..1;
type    Bit_Index is new Natural;

Package Very_Longs contains a type Very_Long that represents arbitrary precision signed integers. Very_Long objects can be manipulated similarly to ordinary integers. The individual bits of the Very_Long object are also easily accessible. Values are stored in "signed-magnitude" form. Negative values are represented internally as their corresponding positive value with a flag set to indicate the negative. This is significant if you access the bits of a negative value.