org.openuat.authentication
Class CandidateKeyProtocol

java.lang.Object
  org.openuat.authentication.CandidateKeyProtocol

public class CandidateKeyProtocol
extends java.lang.Object

This class implements the candidate key protocol (CKP) as presented in Rene Mayrhofer: "Candidate Key Protocol" It is an alternative to Diffie-Hellman key exchange with subsequent key verification. In contrast to DH, it uses only symmetric cryptographic operations and should thus be less resource hungry. Additionally, it does not depend on prior synchronization of the hosts that want to authenticate, but instead hosts can "tune in" to a stream of candidate keys and select those that they also generated locally. It should therefore be well suited for resource limited devices and implicit authentication without any specifc trigger. An additional feature is that it will work with multiple hosts instead of just with one other peer. So multiple instances of the candidate key protocol can be executed concurrently with different hosts with just one instance of this class. In each round, the candidate key protocol collects candidate key parts which will be assembled into a key when both hosts (or all hosts for group authentication) agree on them. As a means of key exchange, a hash value of each candidate key part is broadcast, and other hosts wishing to authenticate with this one may then flag that candidate out of the current list of candidates in this iteration that they also have. A key part can thus go through three phases: 1. Features extracted form sensor data form a candidate key part and get broadcast. 2a. After received a candidate, it is checked against all local candidates. When there is a match, this candidate becomes a matching key part and the candidate's number is signaled to the host that generated it. 2b. The second alternative for advancing a key part from candidate to matching status is to explicitly acknowledge a match. One one host send messages to the sender of the candidate key parts in step 1, indicating which of these parts matched, then the original sender can advance these candidates to match status. Note:Options 2a and 2b are not exclusive. but can be combined. However, they will typically be used in different settings: option 2a for symmetrical settings where each hosts generates and sends candidate key parts, while option 2b can be used for asymmetrical settings where one host sends candidate key parts and the other acknowledges matches. 3. All matching key parts are then assembled into a sliding candidate key, which also gets broadcast. When other hosts hold the same key, they acknowledge it and it can be used for secure communication. Note:The candidate keys generated by the two hosts need not necessarily have the same length in terms of the number of concatenated key parts. When one host has advanced farther than the other in processing local measurements and/or incoming network messages, or messages to the other host have been lost in transit, then it may have found more matching key parts. This means that the other host, when receiving a candidate key message composed of more key parts than it has in its own match list, can not create a matching key. However, this second host will itself broadcast candidate keys as soon as it is ready, and the former will pick up those messages and should, by the virtue of having collected more matches, be able to create a matching key and subsequently acknowledge it. It is therefore not required for the hosts to agree on the number of parts that a candidate key is composed of. After all, it is only a candidate, and the other host does not need to acknowledge it. In short, the whole authentication protocol should be used as follows: 1. Construct the object. 2. For each set of feature vectors that belong together, generate a set of candidate key parts with generateCandidates. These will be kept in an internal history. 3. Send the candidate key parts to the remote host. 4. Test all received candidate key parts with matchCandidates and possibly (depending on the setting, see above for details) send a message signalling the matching one to the remote host. A list of matching key parts will be kept internally. 5. Use getNumTotalMatches and/or getSumMatchEntropy to decide when enough matching key material has been generated and create a candidate key with generateKey. The hash of this candidate key should be sent to the remote host, along with the number of parts used to construct it, and ideally the local and remote index tuples that refer to these parts. These tuples can significantly speed up the next step, because with this information, the specific matching key parts can be concatenated directly without having to perform a full search over all matching parts. Note:This should not reveal any more information to an attacker. As we have to assume that an attacker has more CPU and memory ressources than we do (especially on embedded devices), he/she can already run the searchKey variant that performs a full key search without making use of this information. 6. Test all received candidate key hashes with one of the searchKey variants (preferably making use of index tuples), and, if there is a match, acknowledge that key. At this point, both hosts (or all hosts for group authentication) should hold the same key and can use it for secure authentication.

Version:

1.0

Author:

Rene Mayrhofer

Nested Class Summary

static class	CandidateKeyProtocol.CandidateKey This class represents a complete candidate key, with both the private part (key) and a hash for comparing it with a remote host's candidate (hash).
static class	CandidateKeyProtocol.CandidateKeyPartIdentifier This class represents the complete identification information for a key part candidate.

Field Summary

protected int	totalCryptoTime These are only for keeping statistics on book-keeping, search, and "crypto" times.
protected int	totalListingTime These are only for keeping statistics on book-keeping, search, and "crypto" times.
protected int	totalSearchTime These are only for keeping statistics on book-keeping, search, and "crypto" times.

Constructor Summary

CandidateKeyProtocol(int candidateHistorySize, int matchHistorySize, int maxRemoteMatchListAge, java.lang.String instanceId, boolean useJSSE)
Initializes the candidate key protocol, setting a few parameters and creating the local candidate key parts history.

Method Summary

void	acknowledgeMatches(java.lang.Object remoteHost, int round, int candidateNumber) This function just adds the local candidate key part to the match list that has been reported as match by the remote host.
static java.util.BitSet[]	explodeKOutOfN(int[] set, int k) Returns an array of bit sets, where each of the bit sets represents one combination of choosing k values from the set.
CandidateKeyProtocol.CandidateKeyPartIdentifier[]	generateCandidates(byte[][] candidateKeys, float entropy) Generate a list of candidate key parts out of key parts.
CandidateKeyProtocol.CandidateKey	generateKey(java.lang.Object remoteHost) Generates a candidate key out of all parts currently in the matches list, sorted by the round number.
float	getMatchingRoundsFraction(java.lang.Object remoteHost) Returns the fraction of (local) rounds where at least one matching key part has been found for the specified remote host.
int	getNumLocalRounds(java.lang.Object remoteHost) Returns the number of rounds that have passed during the authentication with the specified remote host.
int	getNumTotalMatches(java.lang.Object remoteHost) Returns the number of entries in the matches list.
float	getSumMatchEntropy(java.lang.Object remoteHost) Returns the sum of all entropy values for matching key parts.
int	matchCandidates(java.lang.Object remoteHost, CandidateKeyProtocol.CandidateKeyPartIdentifier[] candidateIdentifiers) Match an incoming list of candidate key part identifiers with the internal history and report and remember the candidate the matches.
CandidateKeyProtocol.CandidateKey	searchKey(java.lang.Object remoteHost, byte[] hash, int numParts) Tries to generate a key that produces the same hash from the list of matching key parts.
CandidateKeyProtocol.CandidateKey	searchKey(java.lang.Object remoteHost, byte[] hash, int[][] localIndices, int[][] remoteIndices) Tries to generate a key that produces the same hash from the list of matching key parts.
boolean	wipe(java.lang.Object remoteHost) Wipes all state that is held with respect to a remote host.
void	wipeAll() Wipes all entries from the set of matching keys, i.e. calls wipe for all remote hosts where there have been some matches.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

totalListingTime

protected int totalListingTime

These are only for keeping statistics on book-keeping, search, and "crypto" times.

totalSearchTime

protected int totalSearchTime

These are only for keeping statistics on book-keeping, search, and "crypto" times.

totalCryptoTime

protected int totalCryptoTime

These are only for keeping statistics on book-keeping, search, and "crypto" times.

Constructor Detail

CandidateKeyProtocol

public CandidateKeyProtocol(int candidateHistorySize,
                            int matchHistorySize,
                            int maxRemoteMatchListAge,
                            java.lang.String instanceId,
                            boolean useJSSE)

Initializes the candidate key protocol, setting a few parameters and creating the local candidate key parts history.

Parameters:

candidateHistorySize - The number of locally generated candidate key parts to keep in the history. This list will be used to match incoming identifiers and thus serves as a time-window for past matches.

matchHistorySize - The number of matching key parts to keep for each remote host. Out of this matching list, candidate keys will be generated, so the larger this buffer, the more key parts will go into the keys.

maxRemoteMatchListAge - The maximum age for which to keep a list of matching key parts for a remote host, in milliseconds since "the epoch". This is used to keep the number of match histories finite, by pruning lists that have not been updated since this time.

instanceId - This parameter may be used to distinguish different instances of this class running on the same machine. It will be used in logging and error messages. May be set to null.

useJSSE - If set to true, the JSSE API with the default JCE provider of the JVM will be used for cryptographic operations. If set to false, an internal copy of the Bouncycastle Lightweight API classes will be used.

Method Detail

generateCandidates

public CandidateKeyProtocol.CandidateKeyPartIdentifier[] generateCandidates(byte[][] candidateKeys,
                                                                            float entropy)
                                                                     throws InternalApplicationException

Generate a list of candidate key parts out of key parts. This also stores the list in recentKeyParts.

Parameters:

candidateKeys - The list of candidate key parts for the current round.

entropy - The estimated entropy of this set of candidates.

Returns:

A list of candidate key parts that should be sent to the remote host (or group). It will have the same number of elements as the input list of key parts.

Throws:

InternalApplicationException

See Also:

recentKeyParts

matchCandidates

public int matchCandidates(java.lang.Object remoteHost,
                           CandidateKeyProtocol.CandidateKeyPartIdentifier[] candidateIdentifiers)
                    throws InternalApplicationException

Match an incoming list of candidate key part identifiers with the internal history and report and remember the candidate the matches.

Parameters:

remoteHost - An identifier for the remote host that sent the candidate key part identifierts. The same identifier (i.e. equal in the sense of Object.equal) must be passed to subsequent calls to this and other methods when dealing with the same remote host. It can e.g. be an InetAddress object, or an Integer object, defining the remote host ID.

candidateIdentifiers - The incoming identifiers to match against the own history.

Returns:

The index in candidateIdentifiers that points to the matching identifier, or -1 if no match has been found. The tuple of round and candidate number contained in the matching candidate identifier may be sent to the remote host (or group), but does not have to. This depends on the application.

Throws:

InternalApplicationException

acknowledgeMatches

public void acknowledgeMatches(java.lang.Object remoteHost,
                               int round,
                               int candidateNumber)
                        throws InternalApplicationException

This function just adds the local candidate key part to the match list that has been reported as match by the remote host.

Parameters:

remoteHost - An identifier for the remote host that sent the match message. Refer to @see #matchCandidates for more details.

round - The local round number in which this match occured, as received from the remote host.

candidateNumber - The local counter identifiying the matching key parts, as received from the remote host.

Throws:

InternalApplicationException

getNumLocalRounds

public int getNumLocalRounds(java.lang.Object remoteHost)
                      throws InternalApplicationException

Returns the number of rounds that have passed during the authentication with the specified remote host.

Parameters:

remoteHost - An identifier for the remote host. Refer to

Returns:

The number of rounds that have passed with this remote host.

Throws:

InternalApplicationException

See Also:

for more details.

getNumTotalMatches

public int getNumTotalMatches(java.lang.Object remoteHost)

Returns the number of entries in the matches list.

Parameters:

remoteHost - An identifier for the remote host. Refer to

Returns:

The number of matching key parts currently available in the matching list for the specified remote host.

See Also:

for more details.

getMatchingRoundsFraction

public float getMatchingRoundsFraction(java.lang.Object remoteHost)
                                throws InternalApplicationException

Returns the fraction of (local) rounds where at least one matching key part has been found for the specified remote host. A local round is defined by a call to @see #generateCandidates.

Parameters:

remoteHost - An identifier for the remote host. Refer to

Returns:

The fraction of matching rounds with this remote host. By definition between 0 and 1 (inclusive).

Throws:

InternalApplicationException

See Also:

for more details.

getSumMatchEntropy

public float getSumMatchEntropy(java.lang.Object remoteHost)

Returns the sum of all entropy values for matching key parts.

Parameters:

remoteHost - An identifier for the remote host. Refer to

Returns:

The entropy of all matching key parts currently available in the matching list for the specified remote host.

See Also:

for more details.

generateKey

public CandidateKeyProtocol.CandidateKey generateKey(java.lang.Object remoteHost)
                                              throws InternalApplicationException

Generates a candidate key out of all parts currently in the matches list, sorted by the round number. If multiple candidates happen to be in the match list for the same round number, only the first one is taken for this round. This should only happen in a symmetric setting where both hosts report matches, which can lead to double insertion due to differences in timing.

Parameters:

remoteHost - An identifier for the remote host. Refer to

Returns:

The candidate for which the hash, numParts, and index tuple lists should be broadcast. Returns null if no match list has yet been created for the specified remoteHost, either because not matches have yet been received with this host or because it has been pruned due to aging.

Throws:

InternalApplicationException

See Also:

for more details.

searchKey

public CandidateKeyProtocol.CandidateKey searchKey(java.lang.Object remoteHost,
                                                   byte[] hash,
                                                   int numParts)
                                            throws InternalApplicationException

Tries to generate a key that produces the same hash from the list of matching key parts. To search for the possible key, it ideally performs a complete search over all possible keys that can be generated from the list of matching key parts for this host. When this can not be done due to CPU and resource constrains, it falls back to either check only the more recent key parts insted of the whole history, or to use a sliding window of numParts over the local list of matching key parts and, if multiple candidates match for the same round, tries all possible combinations of these candidates.
This can be an expensive operation. It is advisable to use the other variant of searchKey whenever the list of index tuples is available for the received candidate key.

Parameters:

remoteHost - An identifier for the remote host. Refer to

hash - The hash received from the remote host.

numParts - The number of key parts that the key is composed of, as reported by the remote host. Note: This parameter would not be strictly necessary and could be omitted. It is used for better performance in searching for a matching key.

Returns:

The key matching the hash, or null when same hash could not be generated a combination of parts in matchingKeyParts Returns null if no match list has yet been created for the specified remoteHost, either because not matches have yet been received with this host or because it has been pruned due to aging. Also returns null on any other error or cause that leads to a failure in creating a key with the same hash.

Throws:

InternalApplicationException

See Also:

for more details.

searchKey

public CandidateKeyProtocol.CandidateKey searchKey(java.lang.Object remoteHost,
                                                   byte[] hash,
                                                   int[][] localIndices,
                                                   int[][] remoteIndices)
                                            throws InternalApplicationException

Tries to generate a key that produces the same hash from the list of matching key parts.

Parameters:

remoteHost - An identifier for the remote host. Refer to

hash - The hash received from the remote host.

localIndices - The list of index tuples (round,candidate) that reference the parts that have been used to construct the key with the given hash. This list is using the indices of this host. Parts where the index tuples of this host were unknown to the host that generated this candidate key can be set to -1. But either this element or the one in remoteIndices must be set to something >= 0 (this always applies to both numbers in the tuple).

remoteIndices - The list of index tuples (round,candidate) that reference the parts that have been used to construct the key with the given hash. This list is using the indices of the remote host. Parts where its own index tuples were unknown to the remote host that generated this candidate key can be set to -1. But either this element or the one in localIndices must be set to something >= 0 (this always applies to both numbers in the tuple).

Returns:

The key matching the hash, or null when same hash could not be generated a combination of parts in matchingKeyParts Returns null if no match list has yet been created for the specified remoteHost, either because not matches have yet been received with this host or because it has been pruned due to aging. Also returns null on any other error or cause that leads to a failure in creating a key with the same hash.

Throws:

InternalApplicationException

See Also:

for more details.

wipe

public boolean wipe(java.lang.Object remoteHost)

Wipes all state that is held with respect to a remote host. This method should be called when the whole authentication fails as well as when it suceeds. By overwriting key material before freeing the memory, it makes sure that key material will not be kept in memory when it is no longer necessary.

Parameters:

remoteHost - An identifier for the remote host. Refer to

Returns:

true if state was kept for this remote host, false if there was not state to wipe.

See Also:

for more details.

wipeAll

public void wipeAll()

Wipes all entries from the set of matching keys, i.e. calls wipe for all remote hosts where there have been some matches.

See Also:

matchingKeyParts, wipe(java.lang.Object)

explodeKOutOfN

public static java.util.BitSet[] explodeKOutOfN(int[] set,
                                                int k)
                                         throws InternalApplicationException

Returns an array of bit sets, where each of the bit sets represents one combination of choosing k values from the set. This is only public so that JUnit tests can cover it.

Parameters:

set - The set of numbers to choose from.

k - How many to choose from the set. This must be <= set.length

Returns:

The number of numParts (k) out of totalParts (set.length) is (numTotal over numParts) = (n over k) = (n!) / (k! * (n-k)!)

Throws:

InternalApplicationException