Perspective Chapter: Distinguishing Encrypted from Non-Encrypted Data

Abstract

Discriminating between encrypted and non-encrypted information is desired for many purposes. Much of the efforts in this direction in the literature is focused on deploying machine learning methods for the discrimination in streamed data which is transmitted in packets in communication networks. Here, however, the focus and the methods are different. The retrieval of data from computer hard drives that have been seized from police busts against suspected criminals is sometimes not straightforward. Typically the incriminating code, which may be important evidence in subsequent trials, is encrypted and quick deleted. The cryptanalysis of what can be recovered from such hard drives is then subject to time-consuming brute forcing and password guessing. To this end methods for accurate classification of what is encrypted code and what is not is of the essence. Here a procedure for discriminating encrypted code from non-encrypted is derived. Two methods to detect where encrypted data is located in a hard disk drive are detailed using passive change-point detection. Measures of performance of such methods are discussed and a new property for evaluation is suggested. The methods are then evaluated and discussed according to the performance measures.

1. Introduction

The discrimination of encrypted data from other kinds of data is of interest in many areas of application. For instance for making other applications work for the communication traffic in a network where the means for application may depend on whether the traffic data is plaintext/cleartext, compressed, encrypted or encoded in some way. Also, there may be security reasons (e.g. the uncontrolled flow of encrypted data of which some may be transmitted for malicious purposes) which could be an argument for better network supervision tools. To these ends, various methods, mainly of machine learning, have been suggested through the last decades.

1.1 Methods for discrimination in case of streamed data

As a foundation for the treatment, some kind of preprocessing is due. Among methods for this step are the chi-square statistic, Shannon entropy, Kolmogorov-Smirnov statistic, Lilliefors test, Cramér-von Mises statistic, discrete runs test, autocorrelation’s test and the index of coincidence test to mention some [1, 2].

In [1] the problem of filtering encrypted data upon traffic monitoring which is outbound from a computer or a network, so-called egress filtering, is considered. Many aspects and properties of the problem are brought to attention and an extensive account for various evaluation techniques is mentioned.

Different measures for discriminating a given distribution from the normal distribution are the topic in [2]. For discrimination between encrypted and non-encrypted data other distributions than the normal are more relevant but some of the measures considered in this paper can also be used for the more general case.

In [3] machine learning methods are deployed to a fully automated method to the distinction between encrypted and compressed data, claimed to be the first of its kind. A dataset for further evaluation and benchmarking is also provided.

A method for discriminating between compressed and encrypted data in the case when the data is voice over IP with constant and variable bit rate codecs is proposed in [4]. The method is evaluated utilizing the NIST [5] and the ENT [6] test suits.

Reference [7] does not suggest a solution to the discrimination problem but rather a method for fast and distribution true simulation of data reflecting the properties of encrypted and compressed data respectively.

In Ref. [8] a classification procedure, based on Gaussian mixtures and hidden Markov models, is detailed. An elaborate comparative evaluation is carried out taking 9 other attempts to solve the same problem into account. The study concludes that the proposed method renders a better classification at a lower computation complexity.

A lucid convolution neural network method to classify data into being encrypted or non-encrypted is presented by [9]. The proposed method is thoroughly evaluated for various kinds of network traffic and some different performance measures in the field of machine learning.

1.2 Methods for discrimination in case of static data

A different need for discrimination between encrypted and unencrypted data is the following. In police investigations concerning heavy criminality and organized crime where evidence of criminal activity is residing as data on a computer hard disk drive (HDD) the capability to distinguish encrypted files from non-encrypted ones may be primordial [10, 11, 12]. When the police seize an HDD containing data belonging to a suspected criminal, that data can be material of evidence in a subsequent trial. But criminals often try to make sure that the police will be able to use that data. Possible actions to obstruct data access are then to encrypt and/or to quick delete that data. In case of quick delete of data, the pointers to the files are destroyed but the content of the files is still left. The other action is to encrypt files. Using state of the art tools for encryption of files (such as VeraCrypt, Bitlocker, Ciphershed and thereby provided ciphers) there is no general procedure of breaking the encryption other than brute force attack by guessing the cipher algorithm and systematically guessing the encryption key [13]. If some of the files are encrypted and others not, it is then a delicate matter to distinguish between the two if the code has been quick deleted. Nevertheless, the importance of discriminating between encrypted code and plaintext is also stressed by the fact that brute force attacking all clusters of data on the hard drive would be an impossible task while being able to separate the encrypted code from the non-encrypted would make a substantial improvement of the chances for successful cryptanalysis. The police authorities usually have software to brute force those encrypted data but this procedure may be very time consuming if the amount of data is so large that different parts of it have been encrypted with different keys. In juridical cases, time is typically of the essence since the chances of success in prosecution and proceedings against a criminal is depending on deadlines (such as time of arrest, time of trial etc) any time savings in the procedure of extracting evidence from the HDDs is essential. Thus time has to be spent on the appropriate tasks: code-breaking only on the encrypted data rather than trying to decypher non-encrypted data. Given a single file, the task of determining whether it is encrypted or not is usually easy; but given a whole HDD without knowing where the encrypted files are, this is trickier.

There are several software solutions for indicating whether a file is encrypted or not, mostly checking the header of the file and looking for some known pattern like the EFS (Encryption Files System on Windows), BestCrypt, or other softwares’ headers. Such alternatives cannot be used in the case when the user has performed a (quick) delete of the HDD because then the pointers to all files are lost. Nevertheless, the files remain on the HDD: upon deleting a file on an HDD, the pointers to the beginning and end of the physical space on the HDD containing the information of the file are removed. Still, the physical space on the HDD containing the information of the file is not overwritten because that operation would be slow, i.e. as slow as writing the same file again. The operating system’s designers rather leave the file in the HDD intact but indicate that this location is free to host some other data. If nothing has been overwritten, this means that the file is still stored in the HDD for some time which allows recovery software to recover those files.

Recovery software might help to simply recover the files but might also overwrite the data contained in HDD which could result in loss of evidence in case of an investigation. In this case, the police would have to locate the encrypted files without using recovery software or “header-detector” software.

Here methods to locate quick deleted encrypted data are presented and detailed. First, a description of how encrypted data is different from other data is presented. This is followed by the introduction to statistical change-point methods for discrimination between encrypted and non-encrypted data. Finally, the results of these procedures are presented along with some experimental values to evaluate the methods.

However, such a method will only work on mechanical HDDs and not with flash memory devices: in flash memory (like USB memory sticks or Solid State Drive (SSD)), as soon as a file is removed it is erased from the memory because data cannot be overwritten. Therefore as soon as data is deleted, the operating system will choose to delete the pointers and the data to gain time for the time when the user will decide to save data at this location. But erasing in flash memory also takes longer since the pointer have to be deleted and all the files removed which is as long as copying new files on the device.

This application differs from the one mentioned in Subsection 1.1. In the previous case when data is commonly considered being transmitted in packets in a network while here, there is static access to the data. In the previous situation, data consists of sometimes small files where statistical methods for making a foundation indicating if the data is encrypted or not becomes weaker [14] as opposed to the situation here where there is a large amount of data possibly of both kinds, encrypted and non-encrypted. In the previous case with dynamic data in all senses—variable in size, access, time, kind—methods of machine learning which could pick up on the current circumstances were preferable while here, in the case of fixed data, fast and efficient methods of change-point detection becomes a far more advantageous choice. The machine learning methods need training data while the change-point methods can start from scratch with pre-defined parameter values optimized for the situation or with very little run-in data for calibrating the levels. The performance of the machine learning methods is still a matter of research since these are very highly structured procedures, sometimes black box techniques impossible to fully evaluate all properties of, while the change-point detection methods are long since optimized and very thoroughly evaluated from all kinds of aspects of performance through a much longer time.

2. Method

2.1 Description

If encrypted data is not uniformly distributed, the cryptosystem used to cipher those data has a bias and can therefore be attacked. For this reason, characters of the cyphertext produced by any modern high-quality cryptosystem are uniformly distributed [15, 16] i.e. the values of the bytes of the cyphertext are uniformly distributed on some character interval. Indeed, a cryptosystem that does not have this property would be weak since it would be possible to attack it on this bias (distinguishing attacks such as on the RC4 encryption algorithm). The other types of files do not possess this feature although the contents of some types of files are close to being uniformly distributed. The files coming closest without being encrypted are compressed/zipped files: those files are indeed very close to cipher files in terms of the distribution of their character’s byte numbers. Albeit small there is a difference in distribution making it possible to tell compressed files and encrypted files apart.

A technique to quantify this distribution difference is by using chi-square statistic and more or less performing a chi-square test (see [17]) to tell whether the data is suspiciously uniform or not. Another classical method is to calculate the Kolmogorov-Smirnov distance, see e.g. [1, 2] for a more extensive account of ways to indicate whether data are encrypted or not. Procedures building on such preprocessors can then be defined.

One attempt to exploit this distribution difference utilizing the chi-square statistic is [18] where a method to automate the discrimination between encrypted and non-encrypted (i.e. most critically compressed) data into a method with impressing performance. Another approach could be to use means of anomaly detection in the theory of machine learning to develop an adaptive method. The proposed method, however, stems from using statistical change-point detection. The anticipated advantage with this could be the mathematically proven optimality with these methods in terms of efficiency and accuracy under the given assumptions. For many applications, the assumptions of entirely relying on the distribution of the data, in-control and out-of-control are commonly a subject of great controversy. Here, the situation is different though, since the hard drive and its data is not a dynamic system where the content changes its distribution owing to outer time-depending circumstances.

Before going into detail about these methods the preprocessing techniques are introduced.

2.2 Distribution of encrypted data

The working hypothesis is that data (i.e. characters) constituting encrypted files are uniformly distributed, while data of non-encrypted files are not (i.e. differently distributed depending on which type of non-encrypted files). The goal now is to be able to tell an encrypted file from a non-encrypted one.

Let us assume the data constitutes of characters divided into clusters, $c_1,c_2,c_3,\dots$ with $N$ characters in each cluster. The characters that are used range over some alphabet of a set of possible forms. Merging these forms into $K$ classes, the counts $O_{\mathit{kt}}$ of occurrences of class $k$ characters in cluster $t$ are observed. One method of measuring distribution agreement is by means of a ${\chi }^2$ test statistic, $Q_t={\sum }_{k=1}^K{\left(O_{\mathit{kt}}-E_{\mathit{kt}}\right)}^2/E_{\mathit{kt}}$ where $E_{\mathit{kt}}$ are the expected counts of occurrences of characters in class $k$, cluster $t$. Under the hypothesis of uniformly distributed characters, the expected counts of occurrences within each class is $E_{\mathit{kt}}=\frac{N}{K}$ reducing the statistic simplifies to

$$Q_t=\frac{K}{N}\sum _{k=1}^K{O}_{\mathit{kt}}-N$$

the values of which are henceforth referred to as $Q$ scores. Large $Q$ scores indicate deviance from the corresponding expected frequencies $E_{\mathit{kt}}$. The smallest possible $Q$ score being $0$ would be attained if all $E_{\mathit{kt}}=O_{\mathit{kt}}$. The expected value, $E_{\mathit{kt}}$, in each class, should not be smaller than 5 for the statistic to be relevant (5 is a commonly used value; other values like 2 or 10 are sometimes used depending on how stable the test statistic should be to small deviances in tail probabilities). Therefore one should use at least $5$ kB of data in each cluster to enable this test to be relevant. But the larger the number of bytes that are in each cluster, the worse the precision to detect encrypted file values: indeed, if too many bytes were detected as being unencrypted (but were actually encrypted) a large amount of encrypted data might not be detected in the procedure.

Here, the alphabet used was the numbers $0,1,\dots ,255$ representing the possible size in bytes of the characters in the data. These numbers were divided into $K=8$ classes (class 1: values of bytes in $\left\{\mathrm{0,1,2},\dots ,31\right\}$ to class 8: values of bytes in $\left\{\mathrm{224,225,226},\dots ,255\right\}$) and the clusters of size $N=64$ bytes making the expected values in each class $E_{\mathit{kt}}=8$. Assuming that encrypted data are uniformly distributed, the $Q$ scores based on counts of characters in encrypted data are ${\chi }^2$ distributed, see Figure 1 and since 8 classes were chosen, the number of degrees of freedom is $8-1=7$.

Figure 1.

Distribution of the $Q$ scores of encrypted files (obtained by using more than 5000 files) with the distribution function of $Q\in {\chi }^2\left(7\right)$.

2.3 Distribution of non-encrypted data

For non-encrypted data, the distribution is more complicated. Each type of file has its distribution. Consequently, the standardized squared deviances from expected counts under the assumption about uniform distribution are larger and so are the $Q$ scores of the ${\chi }^2$ statistic. However, two problems emerge. Firstly, the size of these increased deviances depends on the type of data—i.e. is the data a text file, an image, a compiled program, a compressed file or some other kind of file?—and how should this information be properly taken into account? Secondly, what is the distribution of the $Q$ score in the case when the data are not encrypted?

To develop a method for distinguishing between encrypted and non-encrypted data it is sufficient to focus on the non-encrypted that is most similar to the encrypted and this turns out to be compressed data. Other types of files such as images, compiled programs etc. commonly render higher $Q$ scores and are therefore indirectly distinguished from encrypted data by a method that is calibrated for discriminating between encrypted and compressed data. About the second question, this is not readily answered. Rather, we just suggest modeling the $Q$ score as being scaled ${\chi }^2$ distributed, i.e. the $Q$ score is assumed to have the distribution of the random variable $\mathit{\alpha X}$ where $\alpha >1$ and $X\in {\chi }^2$. The validity of this approach is sustained by empirical evaluation based on more than 5000 compressed files. The resulting empirical distribution of their $Q$ scores and the distribution of $\mathit{\alpha X}$ where $X$ is ${\chi }^2$ distributed and the value of $\alpha =1.7374$ was estimated by the least square method was plotted in Figure 2.

Figure 2.

Distribution of the $Q$ scores of compressed files (obtained by using more than 5000 files) with the distribution function of $Q=1.7374\cdot X$ where $X\in {\chi }^2\left(7\right)$.

2.4 Change-point detection

Change-point detection [19, 20, 21, 22, 23] is a field of mathematical statistics where the object is to quickly and accurately detect a shift in distribution from on-line observation of a random process. This can be done actively (stop collecting the data as soon as a shift is detected) or passively (continue collecting the data even if a shift is detected in order to detect more shifts). Here passive on-line change-point detection was used to detect if the data from an HDD shifts from non-encrypted to encrypted and vice versa. The change-point detection method is a stopping rule

$$\tau =inf\left\{t>0:a_t>C\right\}$$

where $a_t$ is called alarm function and $C$ threshold. The design of the alarm function defines different change-point detection methods while the values of the threshold reflects the degree of sensitivity of the stopping rule. The alarm function may be based on the likelihood ratio

$$L\left(s,t\right)=\frac{f_{Q_t}\left({\mathit{q}}_t|\theta =s\le t\right)}{f_{Q_t}\left({\mathit{q}}_t|\theta >t\right)}$$

where $f_{{\mathit{Q}}_t}\left({\mathit{q}}_t|A\right)$ is the conditional joint density function of the random variables $\left(Q_1,\dots ,Q_t\right)=Q_t$ given $A$ and where ${\mathit{q}}_t$ is the vector of the observed values of ${\mathit{Q}}_t$. Assuming indpendence of the variables $Q_1,\dots ,Q_t$ the likelihood ratio simplifies to

$$L\left(s,t\right)=\prod _{u=s}^t\frac{f_1\left(q_u\right)}{f_0\left(q_u\right)}$$

where $f_0\left(q_u\right)$ is the marginal conditional density function of $Q_u$ given that the shift has not occurred by time $u$ and $f_1\left(q_u\right)$ is the marginal conditional density function of $Q_u$ given that the shift occurred in or before time $u$.

The conditional density function of the $Q$ score at time $t$ given that the data is encrypted (i.e. uniformly distributed) is

$$f_E\left(q_t\right)=\frac{q_t^{k/2-1}{e}^{-q_t/2}}{2^{k/2}\mathrm{\Gamma }\left(k/2\right)}$$

where $k$ is the number of degrees of freedom, i.e. the number of classes (which in this study is 8 as explained above).

For the non-encrypted files, the conditional density function of the $Q$ score is modeled by $\mathit{\alpha X}$ where $X\in {\chi }^2\left(k\right)$ and $\alpha >1$ supposedly reflecting the inflated deviances from the uniform distribution had the data been encrypted. Thus

$$\begin{array}{c}{f}_{\mathit{NE}}\left(q_t\right)=\frac{\partial }{\partial q_t}\mathbb{P}\left(\mathit{\alpha X}<q_t|X\in {\chi }^2\left(k\right)\right)\\ =\frac{{\left(\frac{q_t}{\alpha }\right)}^{k/2-1}{e}^{-q_t/2\alpha }}{\alpha 2^{k/2}\mathrm{\Gamma }\left(k/2\right)}\end{array}$$

is the density function of non-encrypted data $Q$ score. This means that two cases of shift in didstribution are possible:

• Shift from non-encrypted to encrypted data in which case

  $$L\left(s,t\right)=\prod _{u=s}^t\frac{f_{\mathrm{E}}\left(q_u\right)}{f_{\mathrm{NE}}\left(q_u\right)}={\alpha }^{k\left(t-s+1\right)/2}exp\left(-\frac{\alpha -1}{2\alpha }\sum _{u=s}^t{q}_u\right)$$

• Shift from encrypted to non-encrypted data in which case

$$L\left(s,t\right)=\prod _{u=s}^t\frac{f_{\mathrm{NE}}\left(q_u\right)}{f_{\mathrm{E}}\left(q_u\right)}={\alpha }^{-k\left(t-s+1\right)/2}exp\left(\frac{\alpha -1}{2\alpha }\sum _{u=s}^t{q}_u\right)$$

To detect whether the shift in distribution has occurred or not according to the stopping rule $\tau$ mentioned above, an alarm function should be specified. Two of the most common choices here are:

• CUSUM [24]: $a_t={max}_{1\le s\le t}L\left(s,t\right)$,

• Shiryaev [25]: $a_t={\sum }_{s=1}^{t}L\left(s,t\right)$.

Other possible choices are e.g. the Shewhart method, the Exponentially Weighted Moving Average (EWMA), the full Likelihood Ratio method (LR) and others, see e.g. [20] for a more extensive presentation of different methods.

For the CUSUM alarm function, as $arg{max}_{1\le s\le t}L\left(s,t\right)=arg{max}_{1\le s\le t}lnL\left(s,t\right)$ the alarm function is simplified without any loss of generality by using the log likelihood values instead.

For both cases the alarm functions can be expressed recursively which facilitates collecting and treating the data as follows.

• The alarm function for shift from non-encrypted to encrypted data for the

• CUSUM method is

  $$a_t=\left\{\begin{array}{ll}0& \text{for}t=0\\ max\left(a_{t-1}+\frac{kln\alpha }{2},0\right)+\frac{1-\alpha }{2\alpha }{q}_t& \text{for}t=\mathrm{1,2,3},\dots \end{array}\right.$$

• Shiryaev method is

  $$a_t=\left\{\begin{array}{ll}0& \text{for}t=0\\ {\alpha }^{k/2}{e}^{\frac{1-\alpha }{2\alpha }{q}_t}\left(1+a_{t-1}\right)& \text{for}t=\mathrm{1,2,3},\dots \end{array}\right.$$

• The alarm function for shift from encrypted to non-encrypted data for the

• CUSUM method is

  $$a_t=\left\{\begin{array}{ll}0& \text{for}t=0\\ max\left(a_{t-1}-\frac{kln\left(\alpha \right)}{2},0\right)+\frac{\alpha -1}{2\alpha }{q}_t& \text{for}t=\mathrm{1,2,3},\dots \end{array}\right.$$

• Shiryaev method is

$$a_t=\left\{\begin{array}{ll}0& \text{for}t=0\\ {\alpha }^{-k/2}{e}^{\frac{\alpha -1}{2\alpha }{q}_t}\left(1+a_{t-1}\right)& \text{for}t=\mathrm{1,2,3},\dots \end{array}\right.$$

3. Results

3.1 Evaluation

To quantify the quality of different methods, the performance is compared regarding relevant properties such as the time until a false alarm, delay of a motivated alarm, the credibility of an alarm and so on. The threshold is commonly calibrated against the Average Run Length ${\mathit{ARL}}^0$ which is defined as the expected time until an alarm when no parameter shift occurred (which means that this is a false alarm). It is crucial to have the right threshold values for the methods to perform as specified. Setting the threshold such that ${\mathit{ARL}}^0$ is $\mathrm{100,500,2}500$ and $10000$ respectively (the most common values here are ${\mathit{ARL}}^0=100$ and $500$ but the higher values are also considered since the value of ${\mathit{ARL}}^0$ defines the number of clusters/time points that are treated before a false alarm and the shift could occur very far into the HDD) properties of the methods regarding delay and credibility of a motivated alarm can be compared. Of course, if the threshold is low, this will lead to more false alarms (detection of a change when there is none) but setting a too high threshold will lead to a drop of sensitivity of the method to detect a shift (higher delay between a shift and its detection) and consequently an increased probability of missing a real shift in distribution.

Usually the expected delay, $\mathit{ED}\left(\nu \right)=E_{\nu }\left(\tau -\theta |\theta <\tau \right)$ (expectation of the delay of a motivated alarm; see Figure 1) or Conditional Expected Delay $\mathit{CED}\left(t\right)=E\left(\tau -\theta |\tau >\theta =t\right)$ (expectation of the delay when the change point is fixed equal to $t$) are very important because, for example in health care, the goal is to quickly detect problems to be able to save lifes (Table 1).

$\nu$	Methods
	CUSUM				Shiryaev
	100	500	2500	10,000	100	500	2500	10,000
0.2	4.7844	7.1087	9.5520	11.6905	4.9672	7.3116	9.7634	11.9159
0.15	4.7674	7.0788	9.5109	11.6495	4.8933	7.2409	9.6760	11.8015
0.07	4.7278	7.0162	9.4401	11.5695	4.7455	7.0610	9.4786	11.6114
0.05	4.7176	7.0017	9.4224	11.5420	4.7021	6.9975	9.4308	11.5441
0.02	4.6957	6.9712	9.3860	11.4940	4.6422	6.9144	9.3175	11.4477
0.01	4.6870	6.9581	9.3698	11.4693	4.6150	6.8633	9.2743	11.3973

Table 1.

Values of expected delays $\mathit{ED}$ for the CUSUM and Shiryaev methods for values of ${\mathit{ARL}}^0=100$, $500$, $2500$, $10000$ for a shift from encrypted to compressed data.

However, in the case of detecting encrypted code, expected delays are less relevant as a measure of performance since the data can be handled without any time aspect: the goal is to detect accurately where the encrypted data is located. A method with high expected or conditional expected delay merely means a slightly less efficient procedure.

A more relevant performance indicator, in this case, is for instance the predictive value $\mathit{PV}=P\left(\theta <\tau \right)$ (the probability that the method signals alarm when the change-point has occurred; see Figure 5) or the percentage of detected encrypted files that is discovered while running the process and how to improve it (see Figure 2).

While running the process, the method will stop at some time, $\tau$, and then estimate the change point, $\theta$, by maximizing the likelihood function by using the data after the last previous alarm and the newly detected change-point. This estimated change-point, $\widehat{\theta }$, can be either before or after the true change-point $\theta$. One could increase the intervals where encrypted data were discovered. This would lead to missing less encrypted data (see Figure 2) but also brute-forcing more non-encrypted data (Table 2).

$i$	Percentage
0	CUSUM	Shiryaev
1	0.960254	0.961280
2	0.971053	0.971274
3	0.976242	0.978665
4	0.979266	0.980872
5	0.983681	0.985597
6	0.986248	0.986101
7	0.990101	0.990101
8	0.993371	0.994931
9	0.994326	0.995682

Table 2.

Percentage of encrypted files that are detected when the interval of detected change points $\left[{\tau }_1,{\tau }_2\right]$ is arbitrary replaced by $\left[{\tau }_1-i,{\tau }_2+i\right]$. Typically, with large $i$, the values are very close but not exactly equal to $1$: This happens because the change points are very close (i.e less than 10 clusters for example) and the method does not detect any change. Then no cyphertext is detected at all.

Therefore the difference between the change-points and the alarms according to the method is calculated. Since the proportion of encrypted data relative to the total amount of data on the HDD is unknown, the expected proportion of error is suggested. This is to say, given two change-points, ${\theta }_1$ and ${\theta }_2$, and two stopping times, ${\tau }_1$ and ${\tau }_2$, the expected proportion of error is $E\left(\frac{\mid {\tau }_1-{\theta }_1\mid +\mid {\tau }_2-{\theta }_2\mid }{{\theta }_2-{\theta }_1}\right)$. However, this value has a sense only when there are no false alarms between ${\tau }_1$ and ${\tau }_2$.

If there are false alarms between ${\tau }_1$ and ${\tau }_2$, the proportion of undetected encrypted data was added to the proportion of error to determine the proportion of the error made relative to the size of the encrypted data. Assuming that there are $n$ false alarms ${\tau }_1^{\prime }<\dots <{\tau }_n^{\prime }$ in $\left[{\tau }_1,{\tau }_2\right]$, called expected inaccuracy, or $\mathit{EI}$ for short, is defined as follows.

$$\mathit{EI}=E\left(\frac{\mid {\tau }_1-{\theta }_1\mid +\mid {\tau }_2-{\theta }_2\mid }{{\theta }_2-{\theta }_1}+\sum _{i=1}^{n/2}\frac{{\tau }_{2i}^{\prime }-{\tau }_{2i-1}^{\prime }}{{\theta }_2-{\theta }_1}\right)$$E1

The $\mathit{EI}$ was measured for different values of the parameter $\nu$ in the geometrical distribution of the change-points for different methods (see Table 3 and Figure 3).

$\nu$	Percentage
	CUSUM	Shiryaev
0.20	0.113791	0.116934
0.15	0.112024	0.112757
0.07	0.095589	0.096884
0.05	0.086831	0.088897
0.02	0.062135	0.062066
0.01	0.044261	0.043975
0.005	0.030960	0.030376
0.001	0.016548	0.016028

Table 3.

Expected inaccuracy, $\mathit{EI}$ [see Eq. (1)], for different values of the parameter $\nu$ and for the two methods. For the application of discriminating between encrypted and non-encrypted data on a hard drive this may be considered to be reflecting the degree of fragmentation of the disk; the less fragmentation the farther apart are the change-points and thus the smaller the $\nu$ value, and vice versa.

Figure 3.

Expected inaccuracy $\mathit{EI}$ for the CUSUM (blue graph) and Shiryaev (red graph) procedure. One can see that the Shiryaev procedure is little less accurate when $\nu$ increases but slightly more accurate for small $\nu$ than the CUSUM procedure.

3.2 Complete procedure

The complete process is the method returning a segmentation separating suspiciously encrypted data and most likely non-encrypted data of an HDD; information to be further used to target the brute force cryptanalysis efficiently. This procedure runs a likelihood ratio based change-point detection method and as soon as it detects a change, calculates the maximum likelihood estimator of the change-point to determine where the change-point most likely is located. It will then start over from the location of this estimated change-point with the same method for online change-point detection except that the likelihood ratio is reversed modifying the alarm function to fit the opposite change-point situation, and so on.

3.3 Thresholds and experimental values

The first step is to determine the thresholds rendering ${\mathit{ARL}}^0=\mathrm{100,500,2}500$ and $10000$, for both the CUSUM and Shiryaev methods, for a shift from encrypted to non-encrypted and vice versa. The change-points are commonly geometrically distributed with parameter $\nu$. Here the average time before a change-point is expected to be rather high (several hundred or thousand maybe) as the method deal with 64-byte clusters in an HDD of surely several hundreds of Giga or Tera Bytes. Thus, since $E\left(\tau \right)=1/\nu$, the focus is on very small values of $\nu$ for the methods to be reasonably sensitive.

Commonly values of ${\mathit{ARL}}^0$ are 100 or 500 to make other properties relevant for comparisons. In the case of this application, however, large values of ${\mathit{ARL}}^0$ as $2500$ and $10000$ are studied because the first change-point might not occur until far into the HDD. Adjusting the threshold by simulating data can take very long if ${\mathit{ARL}}^0$ is large ($2500$ or $10000$, especially for the Shiryaev method). In this case, it can take several hours or even up to days to compute the threshold. Therefore, having a way of predicting the threshold by extrapolation would be desired i.e. having an explicit relation between ${\mathit{ARL}}^0$ and the threshold $C$. Intuitively, if ${\mathit{ARL}}^0$ is larger, more data will be taken into account implying a threshold proportionally larger. Indeed, as ${\mathit{ARL}}^0$ increases more data is used in the procedure and the threshold is therefore proportionally increased from how much more data is treated in the procedure. In the CUSUM case, since the alarm function is defined as the log-likelihood ratio, this results in a threshold being a log ${\mathit{ARL}}^0$ (Figures 4 and 5; Tables 4 and 5):

• for a shift from compressed data to encrypted data:

  $$C=0.965524\cdot ln\left(0.030655\cdot {\mathit{ARL}}^0+0.494603\right)$$

• for a shift from encrypted data to compressed data:

  $$C=0.997767\cdot ln\left(0.912316\cdot {\mathit{ARL}}^0+7.294950\right)$$

  For Shiryaev, the threshold is a linear function of ${\mathit{ARL}}^0$:

• for a shift from compressed data to encrypted data:

  $$C=0.647578\cdot {\mathit{ARL}}^0-0.726563$$

• for a shift from encrypted data to compressed data:

  $$C=0.444214\cdot {\mathit{ARL}}^0+0.294281$$

Figure 4.

Expected delays $\mathit{ED}$ for a shift from encrypted to compressed data for the CUSUM procedure (blue) and Shiryaev procedure (red).

Figure 5.

Predictive values for a shift from compressed to encrypted data for the CUSUM procedure (left) and for the Shiryaev procedure (right).

${{ARL}}^0$	Thresholds
	CUSUM		Shiryaev
	${NE}\to E$	$E\to {NE}$	${NE}\to E$	$E\to {NE}$
100	1.2260	4.5801	64.0313	44.1271
500	2.6529	6.1250	323.0625	221.8125
2500	4.2188	7.7120	1618.219	735.4088
10,000	5.5296	9.0990	6475.0547	4441.8413

Table 4.

Values of the thresholds for the CUSUM and Shiryaev methods for ${\mathit{ARL}}^0=\mathrm{100,500,2}\mathrm{500,10}000$ specified for detecting a shift from non-encrypted to encrypted data (indicated by $\mathit{NE}\to E$ for short) and for shift from encrypted to non-encrypted data (indicated by $E\to \mathit{NE}$) respectively.

$\nu$	Methods
	CUSUM				Shiryaev
	100	500	2500	10,000	100	500	2500	10,000
0.20	0.8950	0.9862	0.9984	0.9997	0.9859	0.9984	0.9998	1.0000
0.15	0.8727	0.9805	0.9974	0.9995	0.9736	0.9967	0.9996	0.9999
0.07	0.8031	0.9604	0.9933	0.9986	0.9147	0.9852	0.9976	0.9995
0.05	0.7634	0.9482	0.9907	0.9978	0.8708	0.9754	0.9957	0.9991
0.02	0.6171	0.8942	0.9784	0.9944	0.6927	0.9235	0.9847	0.9964
0.01	0.4712	0.8207	0.9590	0.9890	0.5153	0.8463	0.9661	0.9918

Table 5.

Predictive value $\mathit{PV}\left(\nu \right)=P_{\nu }\left(\theta <\tau \right)$, i.e. the probability that a shift has occurred when an alarm is signaled, for the CUSUM and the Shiryaev methods, for values of ${\mathit{ARL}}^0=100$, $500$, $2500$, $10000$ and with different values of the parameter $\nu$ in the geometric distribution of the change-points.

4. Conclusion

Using the change-point statistical process, a method to detect encrypted data in HDD was successively designed. This method is using the fact that encrypted data is uniformly distributed as opposed to other types of files. The method was designed to detect even a change with the closest files to encrypted files which are compressed data. As this method even detects a small change in the data, any bigger change will be even easier detected. Therefore this process is likely to detect encrypted data among any type of data.

Quick and accurate detection of a change is commonly the desired property of change-point detection methods. In many applications such as medicine, finance, environmental science etc., time aspects of the methods are a matter of interest, e.g. expected delay in detection of a shift or probability of detecting a shift within a specified time interval. Here, however, this time aspect is not of primary interest since the data remain the same during the whole process. Here the need is to detect correctly recognized encrypted data. Therefore the probability of correctly detecting encrypted data is more relevant here. This probability shows that the method detects more than 96% of the encrypted data which is good and by extending the intervals, the method detects more than 99% of the encrypted data. By assuming that the change-points are not too close—which is a plausible assumption since it is unlikely that files are so small if the device is not too fragmented—then the method, by adding a little margin to the intervals, quickly detects 100% of the encrypted data.

The Shiryaev method turns out to be slightly better in the more important respects compared to the CUSUM method. Although the expected delay $\mathit{ED}$ is bigger than CUSUM for large values of the parameter $\nu$ in the distribution of the change points, it is smaller for small values of $\nu$ which is the most relevant case for detecting encrypted data in an HDD. The Shiryaev method also detects more encrypted data than the CUSUM method and has a slightly higher predictive value $\mathit{PV}$.

All in all, this means that both methods designed with the suggested modeling, perform very well with a slight preference to the Shiryaev method for detecting encrypted data in an HDD.

To summarize, a thorough comparison between the proposed method and the aforementioned methods [3, 4, 8, 9, 18] for the situation with streamed data would be the obvious next step in this research. Also other methods, potentially building on the Kolmogorov–Smirnov statistic or the Shannon entropy and by using other anomaly detection of machine learning could be interesting candidates in such a race.

Acknowledgments

The authors wish to express their gratitude to Mattias Weckstén at Halmstad for good ideas and previous readings of the manuscript University and to Linus Nissi (previously Linus Barkman) at the Police Department of Southern Sweden for earlier work in the area.

Conflict of interest

The authors declare no conflict of interest.

Nomenclature

${\mathrm{ARL}}^0$

average runlength in control

${\mathrm{ARL}}^1$

average runlength out of control

ED

expected delay of motivated alarm

CED

conditionala expected delay of motivated alarm given that the change occurred at a specified time-point

PV

predictive value