Ace:Validating Witness and Tokens

Overview

ACE offers a two tiered method for ensuring the validity of hashes. The first tier involved calculating a summary value (CSI) for a set of hashes given to the IMS. These CSIs are composed of all hashes for a given time period (round). This CSI can be used to validate any hash submitted during its round. The second tier involves periodically publishing a witness value that is calculated from all CSI values issues during the previous day.

Issuing Tokens

Tokens are issued to clients after they submit a request. The request contains a hash to secure and a file name. All the hashes for a given time are gathered together and a summary value(CSI) is generated and stored on the IMS. After the round completes and a CSI is generated, clients are given a token that contains enough information to recalculate the CSI for its round. Comparing the recalculated CSI to the CSI stored on the IMS will let clients prove their hashes and tokens are valid.

Here's what happens when a round is closed and a CSI needs to be calculated:

1. All the request hashes are set as the leaf nodes in a tree.
2. requests are paired together and a sha-256 digest is created for the pair. In the case of an odd number of requests, the last three hashes are paired together.
3. The created hashes, Intermediate Hash Value(IHV), are set as the parent nodes for the paired leaf nodes.
4. Similar to the previous pairing, IHV's are paired together and a digest is created for the pairs (or last triplet). This new digest is set as parent to the child IHV's.
5. The previous step is repeated until only one hash remains at the top of the tree, the Aggregated Hash Value(AHV).
6. The new AHV is taken and hashed with the previous CSI to create a new CSI for this round. The new CSI is assigned an ID.
7. A token for each request is generated containing the round ID and proof that will allow a client to regenerate the rounds CSI. See below on how to use this proof to reconstruct the CSI

Validating Tokens and Hashes

Token Overview

A token contains all information needed to validate a hash. A sample token is shown below:

<?xml version="1.0" encoding="utf-8"?>
<token xmlns="http://umiacs.umd.edu/adapt/ace/token/1.0">
        <token-class>SHA-256-0</token-class>
        <digest-service>SHA-256</digest-service>
        <name>/state/myfile.txt</name>
        <round-id>319782</round-id>
        <time-stamp>2008-09-16T14:57:27.936-0400</time-stamp>
        <proof>
                <element index="0">
                        <hash>7957e058645f953f8e2d11c919414adffab7df12df3e7902eb446b02a40ac908</hash>
                </element>
                <element index="1">
                        <hash>9287c2e19f715a67dcb59da8a724084b448dd9382668f347338f1ce20f435872</hash>
                </element>
                <element index="2">
                        <hash>e9cc9417014a43e29870f60504cdbe3c49ba9472b4481bb2ff5f7a68cef147bb</hash>
                        <hash>73384002a2fd512874801fb62e1defbb1902668f04d8a96d6cb90b703d16a506</hash>
                </element>
                <element index="1">
                        <hash>d312e4551a3d3ee6d695d96b8851f3ad1574096305f18d4f052fe853bfe14482</hash>
                </element>
        </proof>
</token>

• token-class: name of the service on the IMS that issued the token.
• digest-service: name of the algorithm used when creating the proof
• name: name of the file this token refers to. This was supplied by the client in a token request.
• round-id: The ID of the round this token was issued in. This is used to request a CSI from the IMS.
• time-stamp: the timestamp for this round
• proof: tree elements that can be used to locally generate a CSI given a files hash.

Calculating CSI from Proof

Calculating the CSI from the proof involved calculating several digests, one feeding into another. The proof that is generated is a snapshot of part of the hash tree that was created for the round. It contains only the tree nodes necessary to generate higher levels of the tree. Since each level in the tree is a summary of lower levels, the proof only needs to contain the summary rather than the entire tree.

The values in the xml proof are the hex encoded values of the digest. See below for converting details.

The list of elements in the proof starts with the leaf nodes listed at the top and contains all levels of the tree through the previous round CSI, which is listed at the bottom. To generate the CSI, you start building the tree at the bottom. To start the tree, you take the hash of the file you are checking at combine it with the hash listed in the proof.

For example, the first element specifies an index of 0. This means the digest for myfile.txt will be inserted first, followed by the proof's hash value. The two byte arrays will be concatenated and a sha-256 digest generated for the array. This generated digest will be inserted into the next higher level of the tree and the digesting process repeated. You repeat the insert and digesting until you have used all used all elements in the proof. The final value is your CSI.

Using the token above, this diagram shows how the tree is rebuild from the bottom up.

Once you have recalculated the CSI for a round, you can request the stored CSI for the round from the IMS and compare the two. If they are equal, then the token and hash is valid. If they do not match, then you either have a corrupt token or hash value.

Calculate CSI

The following java code will calculate the CSI for a given proof. The supplied list of Proof elements contains a list of hashes and an index value just as the token above does.

static String calculateRoot(MessageDigest digest, String localHash,
            List<ProofElement> elements)
    {
        
        byte[] currentHash = asBytes(localHash);
        digest.reset();

        for ( ProofElement element : elements )
        {
            digest.reset();
            int index = element.getIndex();
            int i = 0;

            for ( String hash : element.getHashes() )
            {
                byte[] hashBytes = asBytes(hash);

                // if element.getIndex() is the current index, insert previous hash then continue on
                if ( i == index )
                {
                    digest.update(currentHash);
                    i++;
                }
                digest.update(hashBytes);
                i++;

            }
            // end case, if index is last element in list, then need to append
            if ( index == i )
            {
                digest.update(currentHash);
            }
            currentHash = digest.digest();
        }
        return asHexString(currentHash);
    }

Converting String to byte array

The following java code is used to convert bytes to strings and back again, used in the previous proof conversion.

public static String asHexString(byte[] value)
    {
        String str = new BigInteger(1, value).toString(16);
        if ( str.length() < value.length * 2 )
        {
            str = Strings.repeat('0', value.length * 2 - str.length()) + 
                    str;
        }
        return str;        
    }
    
    public static byte[] asBytes(String hexValue)
    {
        byte[] a = new BigInteger(hexValue, 16).toByteArray();
        byte[] b;
        if ( a.length * 2 == hexValue.length() + 2 )
        {
            b = new byte[a.length - 1];
            System.arraycopy(a, 1, b, 0, b.length);
        }
        else
        {
            b = a;
        }
        return b;
    }

Validating CSIs and the IMS

Validating CSIs against published witnesses is similar to the process for validating a digest against a CSI. The IMS provides the call, createWitnessProofForRound that takes a list of rounds and returns a list of responses containing the witness ID for that round, time the round was signed, and a proof linking that particular round to the witness value.