Identification of Topic Area and Research Aims

Emerging trends in discrete logarithm based kleptography and the need for consideration of these trends in the development of new cryptosystems.

The development of communication technology in the past 100 years has brought about revolutionary changes to how our society interacts. Gone are the days where communication over long distances could only be achieved through the use of the postal system, replaced with technologies such as mobile phones, email and video conferencing. With this new development, new requirements for the security of these communications have arisen. Cryptography, which is the study of how to hide information in plain sight (14), has in various ways always provided answers to these security concerns. Through the use of systems such as public key cryptography, the use of these electronic communication methods is thought to be safe and secure, so many people use these systems with little concern. However, there is a new threat to the security of these systems, particularly to Black-Box Cryptosystems, such as Clipper ((16) and (18)), which are promoted by government agencies, due to their ability to be easy to modify to allow for government viewing of messages in situations relating to criminal activities (16). Enter kleptography, a method of using cryptography to break the security of cryptosystems, and thus gives a third party access to private communications.

This research utilises the methods and research techniques of the fields of cryptography, mathematics and programming to examine and analyse the threat of kleptography to communication security, as well as highlight the need for existing kleptographic attacks to be considered in the design of new cryptosystems. This will be done by considering the various kleptographic attacks available, and implementing these attacks, to discover how difficult it is to implement the theory, and thus access the actual threat posed by these attacks. The emerging trends in kleptographic attacks will also be examined, to aid in focussing on the areas in which countermeasures would be the most effective in preventing the use of these

attacks.

Aims of research

The overall aim of this research is to examine the threat that kleptography poses to cryptography and society’s ability to communicate in a secure manner. Specifically, this research intends to:

1. To demonstrate the necessity of considering the various available kleptographic attacks and kleptographic attack trends when developing and implementing new cryptosystems and communication equipment.

2. To identify the various trends that are emerging in the different types of kleptographic attack available, as well as trends in kleptography overall.

Research Questions

The following questions will be addressed in order to examine the threat the kleptography poses to cryptography and society’s ability to communicate in a secure manner:

RQ		What is the threat that kleptography poses to the use of cryptography, and society’s use of various communication systems?
	SQ1	What is Kleptography?
		SQ1.1		What are Subliminal Channels, and how do they apply to Kleptography?
		SQ1.2		What are some of the common uses and examples of Kleptography?
	SQ2	For Factor Based Public Key Cryptosystems, Discrete Logarithm Based Public Key Cryptosystems and Symmetric Block Based Cryptosystems, what kleptographic attacks exist, and how do they operate?
		SQ2.1		For each cipher, how does the cipher operate?
		SQ2.2		For each cipher, what Subliminal Channels are known to exist?
		SQ2.3		For each cipher, what Kleptography attacks are known about, and how may these attacks be implemented in pseudocode?
			SQ2.3.1		For each attack, what specific countermeasures are known, and how may these countermeasures be implemented in pseudocode?
	SQ3	What general countermeasures exist for Kleptographic attacks, and how may these countermeasures be implemented in pseudocode?
	SQ4	Based on the analysis and pseudocode development, for each considered Kleptographic attack, how can the Kleptographic attack and its countermeasures be implemented in the Java computer language?
		SQ4.1		For each considered Kleptographic attack, what problems exist in actually implementing the Kleptographic attack and it’s countermeasures in the Java computer language?
	SQ5	What trends are present in the current Kleptographic attacks?
		SQ5.1		What conclusions for future Kleptographic attack development can be drawn from these trends?

Research Objectives

To answer the research questions, the following objectives will be undertaken:

1. A literature review to identify:

a. The key terms and theory that is associated with Cryptography and Kleptography, in order to establish a basis for the in-depth mathematics and techniques present in the fields.

b. Past research conducted in the field of Kleptography, to help clarify an appropriate research methodology for the study.

2. Use a case study based research model, which uses textual analysis of primary sources and programming experiments as the data collection methods, to examine:

a. How each cryptographic cipher operates in theory.

b. The Subliminal Channels that are known about in each cipher.

c. The Kleptographic attacks that are known about in each cipher.

d. The countermeasures known for each attack, as well as the general countermeasures that apply to all Kleptographic attacks.

e. How each of these Kleptographic attacks and countermeasures can be theoretically implemented into the Java computer language, using pseudocode.

3. Use the theory uncovered by the data collection, as well as the pseudocode developed for each Kleptographic attack and countermeasure, to implement (code) each Kleptographic attack and countermeasure in the Java computer language, and document any difficulties involved in accomplishing this.

4. Analyse the theory and experimental data gained from the data collection using quantitative group and cross-group analysis to identify and detail:

a. The trends that are present in the various types of current Kleptographic attacks, as well as the trends that are present in the majority of Kleptographic attacks.

b. The possible direction of Kleptographic attack development in the future.

Significance of Research

Contribution to knowledge

This research is significant as it attempts to take a selection of the most common Kleptographic attacks available, and analyse their threat level based on ease of implementation, as well as any trends that emerge on consideration of this selection. More specifically, the research will contribute to:

▪ The development of the field of Kleptography, and Cryptography in general.

▪ The analysis of the various weaknesses that arise in cryptographic ciphers due to Subliminal channels, as well as the development of new Subliminal channels, as compiling known information tends to lead to new ways of looking at that information.

▪ The ability to implement the various Kleptographic attacks and their countermeasures in a variety of computer programming languages, as the pseudocode developed would allow easy implementation, if the various problems associated with transferring the attacks and countermeasures can be overcome, into a multitude of computer languages.

▪ The knowledge of trends that are emerging in Kleptography and Kleptographic attacks in general.

▪ The development of new countermeasures for the various Kleptographic attacks that exist.

Expected outcomes

▪ The research will, upon consideration of the analysis and implementation of the various Kleptographic attacks, determine the actual threat posed by Kleptography. Based on this threat, it is hoped that the appropriate actions will be undertaken

▪ The research generates pseudocode for a number of common Kleptographic attacks and countermeasures, so examination of Kleptographic attacks for countermeasures that are not based on mathematical countermeasures, such as some of the general methods discussed in the Literature Review, will be easier.

▪ The pseudocode and Java computer code developed will allow easier implementation of countermeasures in a variety of computer languages, as the implementer will not require an in-depth knowledge of Cryptography and Kleptography.

▪ The research examines trends in the different types of Kleptographic attack, as well as the trends in Kleptography generally. This will help focus the efforts of Kleptographic countermeasure development, and hopefully lead to newer countermeasures against Kleptography.

▪ The research examines a number of Kleptographic attacks in detail, as well as develops coded implementations of them, and their countermeasures. This sort of information would be useful as an instructional tool, for new students of the field of Kleptography.

Utilization of results

This research is conducted with the intention of producing useful, publishable results in the fields of Kleptography and Cryptography. This research will produce two benefits. Firstly, it will highlight the necessity of considering Kleptography in the design and implementation of new cryptosystems. The research will also contribute to the development of effective countermeasures to Kleptographic attacks, through the analysis of Kleptographic trends. More precisely, the results of the research will provide:

▪ An in-depth analysis, as well as detailed pseudocode, for a range of Kleptographic attacks and countermeasures.

▪ Java computer language code for a range of Kleptographic attacks and countermeasures.

▪ A detailed analysis of the emerging trends in particular types of Kleptographic attacks, as well as in Kleptography overall.

Literature Review

For as long as humans have been able to communicate, they have also strived to restrict the direction of that communication. The field of cryptography is dedicated to such pursuits. However, cryptography is not only concerned with the protection of communications. There is an aspect of cryptography where the tools usually used to secure information, are instead utilised to weaken and expose flaws in existing cryptosystems. This aspect is further split into two sections, that of cryptanalysis and cryptovirology. Cryptanalysis involves exposing these flaws so that stronger, harder to break cryptosystems may be created, whereas cryptovirology involves the use of these techniques for personal gain. This literature review’s focus will be on a subsection of cryptovirology known as kleptography. This review will examine the range of texts that exist in this field. This review will consist of four major sections. Firstly, the background information required to understand the topic will be presented. Next, kleptography will be defined, and then some of the most common kleptographic attacks will be examined. Finally, the common countermeasures used against these attacks are detailed.

1. Background

Due to the complicated nature of this field, some background on the topic is necessary.

1.1 Modulation Mathematics

Modulation Mathematics, or mod maths for short, forms the basis of all

cryptography. It involves the use of a modulus, usually referred to in the notation as N, which is a fixed integer number that all mathematical operations are based around ((10) and (14)). As such, operations are similar to clock arithmetic (in clock arithmetic, the modulus is 12). The following are some examples that illustrate how positive and negative numbers on there own are calculated, from (14, pg 3),

18 (mod 7) = 4 (mod 7) as 7 * 2 + 4 = 18

-18 (mod 7) = 3 (mod 7) as 7 * -3 + 3 = -18

Mathematical operations work in a similar way. For example, when a number is added to another number mod N, the resultant number is calculated as normal (i.e. 7 + 5 = 13), and then checked to see if it is higher than the modulus N. If it isn’t, the resultant number is left as is. If it is, the resultant number is then divided by the modulus, and the remainder from that operation is the answer ((10) and (14)). (14, pg 4) demonstrates how addition and multiplication are carried out under mod maths,

(11 + 13) (mod 16) = 24 (mod 16) = 8 (mod 16) as 24 = 16 * 1 + 8

(11 * 13) (mod 16) = 143 (mod 16) = 15 (mod 16) as 143 = 16 * 8 + 15

1.2 Subliminal Channels

Subliminal Channels are defined as pathways through where information can

pass out of or into a cryptosystem. These channels are to be undetectable during use, and the information carried on the channel is also unreadable, even if an observer knows they are in use ((8, (12) and (24)). These channels are used in most, if not all, kleptographic attacks. They do have one weakness though. As mentioned in (24), the code that uses these channels is easy to identify, so their use in only black-box cryptosystems is essential.

1.3 Public Key Cryptography

Public Key Cryptography is the basis on nearly all the current cryptosystems in

use. It works on the principle of each user of the system having a public key and private key. If a person wants to send a message to the user, they use the public key to encrypt the message, for which the user then uses his private key to decrypt it. The actually implementation of this differs from cipher to cipher, but in most cases, two large primes p and q are generated and multiplied together to gain a public modulus N. A function that is easy to do one way (i.e. encryption or e) but hard to reverse (i.e. decryption or d) is used to convert the message. These functions are called trapdoor one-way functions, as they are very easy to perform one way, but very difficult to perform in the opposite direction without the key (to the trapdoor). There are many different types of these functions. For example, there are functions based on factoring of N (i.e. RSA) and computing discrete logarithms (i.e. Elgamal) ((14) and (24)).

2. What is Kleptography

Kleptography, according to (19), is the “study of stealing information securely and subliminally”. It involves the modification of existing black-box cryptosystems. This modification is achieved though the use of cryptographic techniques, to produce systems that appeared to be functioning correctly, but are leaking information the attacker can use to gain access to their encrypted data. These attacks are used for many purposes, including information ransom or information espionage ((18), (19), (20), and (24)).

3. What are the common Kleptographic attacks

As mentioned in the previous section, kleptographic attacks involve the modification of the underlying hardware and software of a black-box cryptosystem. The actual modification is based on a technique called SETUP, or Secretly Embedded Trapdoor with Universal Protection ((4), (16), (18), (19), (20), (22) and (24)). The SETUP mechanism follows the following specifications, according to (18, pg 3),

Let C be a publicly known cryptosystem. A SETUP mechanism is algorithmic

modification made to C to get C’ such that:

1. The input of C’ agrees with the public specifications of the input of C.

2. C’ computes using the attacker’s public encryption function E (and possibly other functions as well), contained within C’.

3. The attackers private decryption function D is not contained within C’ and is known only by the hacker.

4. The output of C’ agrees with the public specifications of the output of C. At the same time, it contains published bits (of the user’s secret key) which are easily derivable by the attacker but are otherwise hidden. (The output can be generated during key-generation or during system operation).

5. Furthermore, the output of C and C’ are polynomially indistinguishable to everyone (including those who have access to the code of C’) except the attacker.

One point worth mentioning is that to be polynomially indistinguishable, everyone but the attacker can not be able to tell the difference between C and C’ in a time frame that is measured polynomially (rather than exponentially). As explained by (19), there are also various levels of the SETUP mechanism, based around varying levels of the strength of point 5 above. These attacks can be applied to a wide variety of ciphers, from RSA ((4), (18), (19), (22) and (24)), to Elgamal ((18), (19), (20) and (24)) and even symmetric stream ciphers (18). It is shown from this that common attacks exist for nearly every cryptosystem.

4. Common Kleptographic Attack Countermeasures

Since most kleptographic attacks are made due to modification of the underlying hardware and software of black-box cryptosystems, most countermeasures involve verification of the cryptosystem’s integrity ((6), (16), (18), (23), and (24)). For example, most kleptographic attacks work on the basis of using pseudorandom numbers to replace random numbers, so to combat this, one method proposed is to control of the randomness of the cryptosystem should be made accessible to the user. To do this, the cryptosystem’s should have the ability to accept random numbers from the user, as well as generate them itself if the user does not wish to enter the values. The algorithm that the cryptosystem is based on, as well as trusted third party implementations, would also need to be publicly available. In this way, the user could then test the use of the same random numbers in the two implementations of the cryptosystem, and verify they produce the same output ((18) and (24)). The use of third party random number generators is also recommended here, as users tend not to use truly random numbers (18). (18) also proposes countermeasures using system integrity checks and division of duties, where the key’s used by a system and the system itself are produced by different parties.

As can be seen from the previous sections, the use of kleptography to steal information is a concerning trend. There are quite a few different kleptographic attacks available for the wide variety of different cryptosystems available. These include, for example, kleptographic attacks against public key cryptosystems such as RSA, Elgamal and DSA ((4), (18), (19), (20), (22) and (24)). There are also various countermeasures, such as the use of system integrity check to counter the use of these attacks ((6), (16), (18), (23), and (24)), that vary in effectiveness. The literature review reveals the need for more research into this area, particularly in defining how great a threat these attacks are given the known countermeasures, and in the analysis of kleptographic trends, so that newer countermeasures may address these issues. This review, as well as the further refined versions of it created upon the analysis of newer sources, will be instrumental in guiding the research, in particular, by providing the underlying theory as well as a source of data for the various kleptographic attacks and countermeasures that exist. Unless time and effort is dedicated to the field of kleptography, there is no doubt that our communication systems will simply become too unreliable to use.

Methodology

This research is based upon the ontology that it is possible to obtain a complete and accurate model of the world being considered i.e. Naïve realism (2, pg 4). This is informed by work in the fields of Kleptography and Cryptography, which commonly use this ontology due to the ability to accurately determine the properties of information systems, in a software and hardware sense. The epistemological approach that will be taken in this research, which is also influenced by the work in Kleptography and Cryptography, is that of the positivist approach.

The use of these assumptions is based on the reality of the world being considered. Information Technology involves systems in which all aspects of the system can be controlled, and the output can be predicated exactly, thus the ontological and epistemological assumptions made are the closest to the actual nature of the reality been examined.

A study such as the one being proposed obviously requires a method that can examine a number of Kleptographic attacks and countermeasures in a way that allows for an individual and precise analysis of each attack and countermeasure separately. The method also must allow for group and cross-group analysis, for determining emerging trends in the data. Based on this, it has been decided to use a quantitative, case study based approach for the research. Case studies “illustrate, explain, offer more detail or expand quantitative findings” (3, pg 8-8), as well as help “facilitate conceptualisation” (3, pg 8-8). Thus, the method seems suitable to the research, as it allows each attack and countermeasure to be considered as a separate case, which then can be compared and contrasted for emerging trends.

In addition to these points, this methodology is also used extensively in the mathematical and computer science fields (3), as well as almost exclusively in the field of kleptography. A brief examination of the references of this prop