Wednesday, October 22, 2014

52 things Q3: Computational and storage power of different form factors

This is the third in a series of blog posts to address the list of '52 Things Every PhD Student Should Know' to do Cryptography. The set of questions has been compiled to give PhD candidates a sense of what they should know by the end of their first year. We will be presenting answers to each of the questions over the next year, one per week, and I am the student assigned to the third question:

Q3: Estimate the relative computational and storage capabilities of
  • a smart-card
  • a micro-controller (i.e. a sensor node)
  • an embedded or mobile computer (e.g., a mobile phone or PDA)
  • a laptop- or desktop-class computer.

To measure the computational capability of a device we could assess the clock speed of its processors. This may be misleading if the processor enables some form of parallelism---two cores running at 2 GHz obviously possess more computational power than a single core running at 2 GHz, and so finding a direct quantitative measure is not a realistic expectation. For specific devices like general purpose graphics cards, often the total FLOPS (floating point operations per second) the device is capable of sustaining is reported (for either single or double precision arithmetic) but even this measure is not a particularly reliable choice when applied to any given problem---indeed, some services facilitate a comparison by benchmarking the performance of different devices on a variety of problem instances---see, for example, CompuBench. Fortunately the range of capabilities of the devices included in the question makes a sufficient answer less dependent on quantitative metrics.

A measure for the storage capabilities of each device is much simpler to find: we can simply compare the approximate number of bytes of information the device is capable of holding on permanent storage.

A smart-card is the least computationally powerful device: obviously clock speeds vary for different implementations, but one might expect to see around a 20 MHz core speed. In terms of storage, a typical smart-card might have around 2 kilobytes (KiB) available.

A microcontroller is "a small computer on a single integrated circuit containing a processor core, memory, and programmable input/output peripherals" [1]. The range of storage and compute capability available will vary significantly according to the exact definition of microcontroller, but taking the suggested sensor node as an example, a typical microcontroller is likely to have similar computational capabilities as a smart-card and slightly more storage available, perhaps in the order of a few KiB to a few megabytes (MiB).

A mobile computer such as a mobile phone has significantly more storage and computing power, and the amount of power available is rapidly increasing over time. Taking the 2008 iPhone and the 2013 Nexus 5 phone as an example, the iPhone used a 412 MHz 32-bit RISC ARM core, and the Nexus 5 CPU used is a 2.3 GHz quad-core processor. In terms of storage, if we ignore the ability of some phones to use removable storage, then a high-end phone in 2013 might expect to provide in the order of 16 to 32 gigabytes (GiB) of storage

Finally, most laptop or desktop class computers are likely to have more processing power than a mobile phone: the high-end Intel "Haswell" i7 4960K processor contains 4 cores each clocked at 4 GHz, and the AMD "Piledriver" FX-9590 CPU contains 8 cores at 4.7 GHz---note that a direct comparison between these two processors requires more than just assessing core counts and clock speeds! There are other factors that can affect the computing capabilities of a desktop or laptop computer---in particular, the addition of a graphics processing unit can, for certain problems, provide a large increase in performance. The storage capacity of a laptop or desktop can vary tremendously, but a typical amount of storage in a consumer machine might be between hundreds of gigabytes and several terabytes (TiB)---the largest single hard drive capacities are now around 8 TiB.

  • [1]

Friday, October 17, 2014

Study group: witness-indistinguishable proofs (2014-10-16)

Zero-knowledge (ZK) proofs are a fairly common object in cryptography. What's less common knowledge: zero-knowledge does not compose well. For example, for every interactive ZK prover/verifier (P,V), you can build another pair $(\overline P, \overline V)$ that is still a ZK proof of the same language but running two prover/verifier instances in parallel leaks a witness.

Back in the early days of ZK, Feige and Shamir came up with an alternative notion called witness indistinguishability (WI). This says that (for some NP language) if $v, w$ are two witnesses to a statement $x$ then a proof using $v$ is indistinguishable from one using $w$. For some languages like "discrete logarithms" this property holds trivially but once there are several witnesses it becomes interesting. For example, a WI proof of a witness to a Pedersen commitment $G^x H^r$ is guaranteed not to reveal $x$, just like the original commitment itself. And WI is closed under composition. In fact, you can do a strong (and composable) form of WI that is information-theoretic and holds even if the verifier knows the witnesses in question, i.e. the proof is statistically independent of the witness.

The second topic we looked at are ZAPs. No-one seems to know what ZAP stands for but it's a two-round WI proof in the plain model (plain-ZK would require at least 3 rounds). The idea: start with a "common random string"-model non-interactive ZK scheme. In round 1, the verifier picks a lot of random strings $r_1, \ldots, r_k$. In round 2, the prover picks one random $r$ and sets $c_i = r_i \oplus r$ to get $k$ different CRS values. The prover then sends a CRS-NIZK proof for each of these values; the verifier accepts if all of them verify. An argument on the probability of a proof for a false statement going through on a random CRS then says that the soundness error of this construction is negligible in $k$.

At CRYPTO '03, Barak et al. further showed how to derandomise ZAPs.

Our final application is a 3-round OT scheme. To transfer a bit, verifier picks an RSA modulus $N = pq$. The prover sends a random string $r$  and the verifier replies with two random elements $y_0, y_1$ and a ZAP  w.r.t. $r$ that at least one is a quadratic residue $mod N$. The prover then picks two random $x_0, x_1$ and sends $y_0^{b_0} \cdot x_0^2$ and $y_1^{b_1} \cdot x_1^2$. The verifier can recover one bit by checking which of the two values is not a quadratic residue. To OT a whole bitstring, this protocol can be done for all bits in parallel. This is where it is important that the ZAP (which is WI) still works under concurrent composition.

Thursday, October 16, 2014

52 Things: Number 2: What is the difference between a multi-core processor and a vector processor?

On the face of it, you may be confused as to what the difference is between these two processors. After all, you may be familiar with words like parallel computing and come across these two different types of processor. So what are the differences between them? This is the question of this week’s 52Things Every Cryptography PhD Student should know. But before we get into the nitty gritty of it, why don't we first have a look at the concept these two different processors are part of, namely parallel computing.

What is parallel computing?

Before answering this question we first need to consider the conventional “serial” model of processing. Let's do so by imagining some problem we need to solve. The way serial computing solves this problem is by viewing it as a number of steps (instructions) which the processor deals with in sequential order. The processor deals with each of the instructions and then at the end, the answer comes out and the problem is solved. Whilst being a wonderful way of solving the problem it does however imply a bottleneck in the speed of solving it. Namely, the speed of the processor at executing the individual instructions. This is fine if the problem isn’t too large, but what happens when we have to deal with larger problems or want to compute things faster? Is there a way of increasing the speed of computation without the bottleneck of the speed of the processor?

The answer as you might have guessed is yes and it comes in the form of something called parallel computing. What parallel computing does to the problem we are trying to solve is to break it down into smaller problems, each of which can be computed separately at the same time. In this way, the problem is distributed over different processing elements which perform each of these different sub problems simultaneously, providing a potentially significant increase in speed of computation – the amount of speed up depends on the algorithm and can be determined by Amdahl's law [1]. So how does this all work? How can you process things in such a way as this? Well two solutions to the problem are multi-core and vector processors.

What is a multi-core processor?

A multi-core processor is a single computing component that carries out parallel computing by using multiple serial processors to do different things at the same time. The sub problems of the bigger problem discussed earlier are each solved by a separate processor allowing programs to be computed in parallel. It's like having multiple people working on a project where each person is given a different task to do, but all are contributing to the same project. This might take some extra organising to do, but the overall speed of getting the project completed is going to be faster.

What is a vector processor?

A vector processor is a processor that computes single instructions (as in a serial processor) but carries them out on multiple data sets that are arranged in one dimensional arrays (unlike a standard serial processor which operates on single data sets). The idea here is that if you are doing the same thing many times to different data sets in a program, rather than executing a single instruction for each piece of data why not do the instruction to all the sets of data once? The acronym SIMD (Single Instruction Multiple Data) is often used to denote instructions that work in this way.

What is the difference?

So that's the general idea, let's sum up with an example. Let's say we want roll 4 big stones across a road and it takes one minute to do each roll. The serial processor rolls them one by one and so takes four minutes. The multi core processor with two cores has two people to roll stones so each one rolls two stones, it takes two minutes. The vector processor gets a long plank of wood, puts it behind all four stones and pushes them all in one, taking one minute. The multi core processor has multiple workers, the vector processor has a way of doing the same thing to multiple things at the same time.


Friday, October 10, 2014

Compiler-based side-channel application and masking

This weeks study group was led by David McCann and focused on the “Compiler-based Side Channel Vulnerability Analysis and Optimized Countermeasures Application” [1] paper presented at the Design and Automation Conference (DAC) 2013. At a high-level, the authors consider the output for each instruction executed and determine, for each individual bit, the minimum number of key bits mixed into the result. Using this information, the compiler makes a decision (based on a threshold) on whether or not to mask the intermediate data.

Consider a toy example of the AddRoundKey operation from AES where $s = k \oplus m$ where $m$ is the input matrix, $k$ is the key matrix and $s$ is the resulting state matrix. Each bit of $s$ contains only a single bit of keyed information. The authors define security as a threshold for the minimum number of key bits affecting each intermediate state bit. The exception being an intermediate state bit that has no relation to the key bits (in this case, the security is considered infinity).

The authors incorporate the additional stages, referred to as the “security-oriented data flow analysis” (SDFA), into the LLVM compiler framework. This has some immediate advantages over applying masks directly in the source code, specifically, if the source code applies a masking scheme, and the compiler is clever enough to notice, the masking process may be identified as unnecessary computation and be optimised out. In addition to this, only the vulnerable intermediate bits are identified for masking rather than the application as a whole.

The SDFA converts the compiler intermediate-representation (IR) code to a Control-Flow Graph (CFG) where each node represents a statement in the program. The authors go on to define a set of rules for the propagation of keyed information at the input and output of the and, or, cmp, mul, div, mod, store, load and shift operations. I could define all the rules here, however this would be almost equivalent to re-writing the paper so if you are interested, please read the full text [1].

In the final section, the authors present experimental results with an implementation of AES-128. The results are compared to implementations presented in [2] and [3]. They discuss different levels of masking and their respective code size and speed performance. The authors highlight the speed-up in performance over existing masked implementations (roughly x2.5).

It is a nice and neat presentation on how to exploit the compilers framework to identify and mask vulnerable intermediate data. I am on the fence about the speed-up results seeing as the reference implementations are optimised for 8-bit processors (whereas the target hardware was a 32-bit processor). They also state the code size increase in their work is 'acceptable' given the speed up. However there is a three fold increase in size for a first order tabulated S-Box (accredited to loop-unrolling) for a two fold speed-up. Nevertheless, a nice paper with good potential for automation of side-channel countermeasures.

Plaintext Awareness and Signed ElGamal

For the first study group of the academic year, David Bernhard spoke on recent developments in the area of CCA-secure public key encryption. After introducing the security goals of the area and some key previous results, he presented a paper by Yannick Seurin and Joana Treger, from CT-RSA 2013 [0], which aims to provide such a scheme, which is a variant of Schnorr-signed ElGamal encryption...

ElGamal Encryption

We begin with a recap of the ElGamal encryption scheme. ElGamal is a public-key cryptosystem whose security is derived from the security of the discrete logarithm problem (DLP). Very briefly, it uses a publicly known cyclic group $G$ (in which the DLP must be hard!) of prime order $p$, with a chosen generator $g$. The user setting up the scheme picks a secret variable $x$, and sets their public key to be $h:=g^x$. To encrypt a message $m$ under this public key, one sends sends the pair $(g^y,mh^y)$, which the initial user can decrypt since they know $x$ and $p$.

ElGamal encryption is IND-CPA secure if (and only if) the Discrete Diffie-Hellman (DDH) assumption holds[1]. However, its ciphertexts are malleable and thus the scheme cannot be IND-CCA2. Indeed, trying to extend it to such a scheme turned out not to be as simple as one might think. Various papers made progress in this direction, taking two rather different directions. One branch aimed to create a hybrid scheme (e.g. DHIES [2]) and reduces security to a stronger assumption on the group and that of the symmetric primitive used. The method we will look at is the alternative...


Plaintext Awareness

A scheme is said to be plaintext aware in the Random Oracle Model (ROM-PA) if an adversary cannot generate a valid ciphertext without already knowing the plaintext of it. That is, it encapsulates the behaviour of a good scheme that prevents the adversary from generating valid ciphertexts other than by encrypting plaintexts herself (or doing something she knows to be equivalent to this). The technicalities of this definition are rather complex, but roughly mean that that given a ciphertext and the list of random oracle queries made to generate it, one can deduce the underlying plaintext.

Now, the key result for us is that if a scheme is both IND-CPA and ROM-PA secure, then it is IND-CCA2 secure [3].


Making ElGamal ROM-PA

Various earlier results had considered designing a plaintext aware scheme by combining ElGamal with a Schnorr signature [1,4], forming a scheme this paper refers to as SS-EG. Whilst SS-EG inherits IND-CPA security from ElGamal, unfortunately it does not add plaintext awareness. The key contribution of this paper[0] was to observe that actually SS-EG is in some sense "very close", and define a very similar scheme using Chaum-Pedersen commitments rather than the Schnorr signatures. Denoted CPS-EG, the only real difference between the schemes is a slight modification to the variables in the ciphertext and the addition of two more variables to the Random Oracle query when generating the commitment. It is the second of these differences that is criticial, because the extra information supplied to the random oracle (information that an extractor is given direct access to) is sufficient to make the scheme ROM-PA.

Making ElGamal IND-CCA2

At this point, one may hope that the scheme is indeed IND-CCA2, but there remains one final twist. There are various different ways one may transmit the required data for a signature, of which one traditional method is the Fiat-Shamir scheme, consisting of a challenge commitment and appropriate response (i.e. a non-interactive proof of knowledge). However, there are also alternative representations that are more efficiently packaged, leading to more concise ciphertexts. The particular representation chosen in the original scheme in fact failed to inherit IND-CPA security from the underlying encryption scheme [5].

Returning to the (less concise) Fiat-Shamir scheme ensures the final version of CPS-EG is indeed an IND-CCA2 secure public key encryption scheme.


[0] A Robust and Plaintext-Aware Variant of Signed ElGamal Encryption
Yannick Seurin and Joana Treger
CT-RSA 2013

[1] On the Security of ElGamal Based Encryption.
Yiannis Tsiounis and Moti Yung
PKC '98

[2] The Oracle Diffie-Hellman Assumptions and an Analysis of DHIES
M. Abdalla, M. Bellare and P. Rogaway
CT-RSA '01

[3] Relations among notions of security for public-key encryption schemes
M. Bellare, A. Desai, D. Pointcheval and P. Rogaway
Crypto '98

[4] A practical mix
Markus Jakobsson
Eurocrypt '98

[5] Cited by authors as 'personal communication'
Bertram Poettering
Jan 2013

Thursday, October 9, 2014

52 Things: Number 1 : Different Types of Processors

This is the first in a series of blog posts to address the list of '52 Things Every PhD Student Should Know' to do Cryptography. The set of questions has been compiled to give PhD candidates a sense of what they should know by the end of their first year - and as an early warning system to advise PhD students they should get out while they still can! In any case, we will be presenting answers to each of the questions over the next year and I have been volunteered for the (dubious) honour of blogging the very first 'thing'. The first topic is on computer architecture and is presented as the following question:

What is the difference between the following?
- A general-purpose processor.
- A general-purpose processor with instruction-set extensions.
- A special-purpose processor (or co-processor).
- An FPGA.

There is no strict definition of a general-purpose processor, however, it is widely accepted that a processor is general if it is Turing-complete. This captures any processor that is able to compute anything actually computable (i.e. can solve any problem a Turing machine can). I will not delve into the definition of a Turing machine but if I've already lost you then I would recommend brushing up on your Theory of Computation [1]. Note though that this definition has no concept of performance or instruction-set capabilities and, in fact, some researchers have gone through the trouble of proving that you may only need a single instruction to be Turing-complete [2]. In the context of modern processors, most programmable CPUs are considered general purpose.

The cost of being general-purpose usually comes at a penalty in performance. Specifically, a general-purpose processor may be able to compute anything computable but, it will never excel at complex repeated tasks. Given a task that is repeated regularly on a general-purpose processor in a wide variety of applications, a processor designer may incorporate instruction-set extensions to the base micro-architecture to accommodate the task. Functionally, there may be no difference in the micro-architecture capabilities but practically there may be huge performance gains for the end-user.

As we're all cryptographers here, I will stick to a crypto example for instruction-set extensions. Consider a desktop machine with an AES encrypted disk. Any reads from secondary storage require a CPU interrupt to decrypt the data blocks before being cached. Given disk access from a cache miss is already considered terrible, add the decryption routine over the top and you have a bottleneck worth making you re-consider your disk encryption. It should be clear here that AES is our complex repeated task and given a general-purpose CPU with a simple instruction-set, we have no choice but to implement the decryption as a linear stream operations. Intel and AMD both recognised the demand for disk encryption and the penalty AES adds to secondary storage access and have (since circa 2010) produced the AES-NI x86 instruction-set extension to accelerate disk encryption on the their line of desktop CPUs.

If you want to fully accelerate any computation, the most optimal result will always be a special-purpose processor or an Application-specific integrated circuit (ASIC). Here we lose a significant portion of the flexibility granted by a general-purpose processor in exchange for performance gains. These types of processors are often tightly-coupled to a general-purpose processor, hence the term co-processor. Note, a co-processor may indeed be in the same package as a general-purpose processor but not necessarily integrated into the general-purpose architecture. Once again, if we turn to modern processor architectures, Intel and AMD have both integrated sound cards, graphics processors and DSP engines into their CPUs for some time now. The additional functionality is exposed via special-purpose registers and the co-processor treated as a separate component which the general-purpose processor must manage.

Finally we turn to Field-Programmable Gate Arrays (FPGAs). The middle-ground between ASIC and general-purpose processors. If an application demands high-performance throughput but also requires (infrequent) modification then an FPGA is probably the answer. To understand how an FPGA works, consider a (very) large electronics breadboard with thousands of logic-gates and lookup tables (multiplexers attached to memory) placed all around the breadboard. If you describe an application as a set of gates and timing constraints then you can wire it together on the breadboard and produce a circuit that will evaluate your application. An FPGA affords the flexibility of being re-programmable whilst producing the dedicated logic to evaluate a target application. The key difference to a general-purpose program is how you design and build your application. In order to get the most out of the hardware you must describe the application as a set of hardware components and events using a hardware description language (Verilog or VHDL). This process is frequently used to prototype general-purpose and special-purpose processors on FPGAs before production. However, it is not without its drawbacks. Designing a program with low-level building blocks becomes very cumbersome for large applications. In addition, the energy consumption and hardware costs are generally higher in comparison to a general-purpose embedded IC. Recently, FPGA manufacturer Xilinx have begun shipping FPGAs with ARM general-purpose cores integrated within a single package [3]. This now makes FPGAs available to the ARM core as a flexible co-processor. As a result, you can build dedicated logic to evaluate your crypto primitives and hence accelerate cryptographic applications.

In summary, general-purpose processors are capable of computing anything computable. Similarly for a general-purpose processor with instruction-set extensions and it may perform better in particular applications. A special-purpose (or co-processor) is very fast at a particular task but is unable to compute anything outside of that. An FPGA can be used to build all of the above hardware but sacrifices speed for flexibility over an ASIC solution.

Monday, October 6, 2014

EM is beginning to lose the non-invasive touch

Anyone familiar with hardware side-channel attacks knows that electromagnetic (EM)-field attacks are considered the most practical and forgiving attack vector. This is owing to the non-invasive and localisation properties of EM-fields. We note this in contrast to early differential power analysis (DPA) [1] attacks which require a direct power tap (and often some modification to the target circuitry).

A recent publication at CHES2014 [2] seeks to challenge the state of EM-field attacks in an attempt to detect and subsequently prevent EM side-channel attacks. Prior attempts have been made to design an EM 'concious' devices (either by EM noise generation or active EM shielding [3]) but these have come at a heavy cost to area and power consumption, both of which are often of higher priority than security in an integrated circuit (IC) development cycle. This recent publication addresses these constraints and presents a simple and elegant solution to foil EM-field attacks.

First, let's recall the stages of an EM-field side-channel attack. An adversary must first buy/capture/'borrow' a target device. Having successfully gained physical access to the device, they must now establish a method to capture the EM-field side-channel leakage. A standard setup will include an near-field probe, an amplifier and a digitizer/oscilloscope. The probe is placed over an (experimentally determined) area of interest and the  adversary will record the EM-field radiation during the execution of some cryptographic operations. Additional information may be requires for specific attacks (ciphertexts or plaintests) but we'll stick to a generic scenario here.

In [2], the authors present a design methodology which allows the IC to detect probing attempts and prevent an attack early on in the process. The authors exploit the physical laws of EM-fields and mutual inductance to detect frequency shifts in the side-channel leakage owing to a near-field probe being placed in close proximity to the IC. If we consider the EM-frequency on the surface of the target IC as a result of some inductance ($L$) and capacitance $(C)$ we can calculate the frequency as follows:

$f_{LC} \approx \frac{1}{2\pi\sqrt{LC}}$

With the introduction of an EM-field probe, we expect the probe coil to produce its own field and hence a some form of mutual inductance ($M$) on the IC surface. The (shifted) EM-frequency at the IC surface will then present as:

$\bar{f}_{LC} \approx \frac{1}{2\pi\sqrt{(L-M)C}}$

We expect the mutual inductance to be inversely proportional to the distance between IC surface and the probe. Hence, as the probe approaches the surface, the frequency shift increases. At a high-level, the countermeasure detects the frequency shift and alerts the cryptographic core to the attack. However, any IC designer will point out, analogue circuity requires a careful design process and is often restrictive and costly. In addition, capturing a reference frequency may not always be possibly if the adversary has unfettered access to the device. The authors realise this and present a clever dual-coil control and detection logic implemented with a standard cell library and a MOS capacitor bank. This allows the entire design workflow to be (semi-)automated and hence greatly reducing the development time and resource constraints. We'll not go into the details of the design here but you can pick up all the information from their paper on eprint [2].

As a proof-of-concept design, the authors produced an $0.18\mu m$ process ASIC with an AES core and their EM detection logic. They proceeded to test the ASIC under a few different attack scenarios ranging from a vanilla EM attack to an adversary who is completely aware of the countermeasure and attempts to circumvent it. In all scenarios, the detection logic was able to pick-up the EM-probe and assert the control logic to halt the cryptographic operations. Arguably a solid result for the design team. The paper presents the system in a very nice and neat package for IC designers to pick up and implement. With relatively low overhead costs ($2\%$ area, $9\%$ power and $0.2\%$ performance) it is hard to argue against it. However, it is not without a few caveats.

The detection system will not be able to detect all EM attacks and the authors do acknowledge this in their conclusion. However they do not discuss this in any great detail. Having no access to their device I can guess at a few scenarios in which their system is too limited to detect an attack. Primarily (from my understanding) the authors always depackage the device (normally unnecessary when dealing with EM-field side-channel attacks and defeating the purpose of its non-invasive nature) and measure the probe distance relative to the die surface rather than the IC surface. There seems to be little mention on the effectiveness when with the device package still intact. Furthermore their current approach is limited to detecting probes from a maximum of $0.1mm$ to the die surface whereas EM leakage can picked up at far greater distances [4]. There is also the prospect that an adversary will not position the probe above the IC itself but over the support circuity around the IC (i.e. decoupling capacitors and power regulators). In this scenario, the countermeasures will be unable to detect any shift. Finally, there is little discussion on false-positives. All electrical devices will produce some form of mutual inductance and capacitive coupling so if we consider a device deployed in the field with these countermeasures. Will placing it near my smartphone (which contains several antennas and ICs) stop the device from performing any cryptographic operations? For its practical shortcomings though, this paper is a solid move in the direction to preventing EM side-channel attacks. Their design methodology and workflow make it appealing for practitioners and the simplicity behind their approach minimises the cost for IC manufacturers, overall a good contribution to the literature.