We show attacks allowing an off-path attacker to intercept and modify IP
packets, and to poison the cache of DNS resolvers.
Our attacks are all by off-path spoofing adversary, i.e., do not require
eavesdropping abilities.The attacks allow circumvention of security
mechanisms assuming that attackers cannot eavesdrop, e.g., Same-Origin
Policy, motivating the adoption of cryptographic defenses (with security
against MITM adversary).
Based on joint works with Yossi Gilad and Haya Shulman.
Yao's garbled circuit (GC) construction is a central tool for
constant-round secure computation and has several other applications. The
GC transformation maps a boolean circuit C into a "garbled circuit" C', and
an n-bit input x into a short "garbled input" x', such that C'
together with x' reveal C(x) and no additional information about x.
Crucially, the mapping from x to x' is simple (e.g., affine) and the length
of x' does not depend on the size of the circuit. In applications, the
latter property leads to low online complexity, as one can typically
compute C' ahead of time.
We present two new garbled circuit constructions extending the scope and
improving the efficiency of known constructions.
(1) We reduce the size of the garbled input x' from n*k to n+k, where k is
the security parameter. This gives rise to a GC with *optimal* asymptotic
rate of 1. As an application, we obtain protocols for secure multiparty
computation and non-interactive verifiable computation in the preprocessing
model which achieve, for the first time, an optimal online communication
complexity.
Based on a joint work with Yuval Ishai, Eyal Kushilevitz and Brent Waters.
(2) We show how to garble *arithmetic* circuits in which the input x
consists of n integers from a bounded (but possibly exponential) range.
This is the first extension of the GC technique to the arithmetic setting.
Based on a joint work with Yuval Ishai and Eyal Kushilevitz.
10.25
דר' ערן יהב, הטכניון
Differential Program Analysis for Exploit Generation
We address the problem of computing semantic differences between a program
and a patched version of the program. Our goal is to obtain a precise
characterization of the difference between program versions, or establish
their equivalence when no difference exists. By analyzing a program and its
patched version, we can verify that the patches we release do not expose the
patched exploit in an obvious manner.
We focus on computing semantic differences in numerical programs where the
values of variables have no a-priori bounds, and use abstract interpretation
to compute an over-approximation of program differences. Computing
differences and establishing equivalence under abstraction requires
abstracting relationships between variables in the original program and its
patched version. Towards that end, we first construct a correlating program
in which these relationships can be identified, and then use a correlating
abstract domain to compute a sound approximation of these relationships. To
establish equivalence between correlated variables and precisely capture
differences, our domain has to represent non-convex information. To balance
precision and cost of this representation, our domain may over-approximate
numerical information as long as equivalence between correlated variables is
preserved.
We have implemented our approach in a tool built on the LLVM compiler
infrastructure and the APRON numerical abstract domain library, and applied
it to a number of challenging real-world examples, including programs from
the GNU core utilities, Mozilla Firefox and the Linux Kernel. We evaluate
over 50 patches and show that for these programs, the tool often manages to
establish equivalence, reports useful approximation of semantic differences
when differences exists, and reports only a few false differences.
Following the advances in the cryptanalysis of hash functions in the last
years, and especially the alarming results on SHA1 and Merkle-Damgard hash
functions, NIST has started a cryptographic competition to offer secure
and fast hash function standard, to be named SHA3. The competition,
currently at its third and last phase (with 5 remaining candidates), is
the focus of many efforts in cryptanalysis and implementation.
In this talk, we shall cover some of the aspects of this competition,
starting from the reasons that led to it, through the first and second
phases, the 5 finalists, their status (both security-wise and
performance-wise), and of course, what is expected to happen when the
SHA3 competition ends.
13.40
יוסי אורן, אוניברסיטת תל אביב
The Mechanical Cryptographer: Tolerant Algebraic Side-Channel Attacks using pseudo-Boolean Solvers
Machine solvers are a class of general-purpose software tools which input a
set of equations and output a satisfying assignment to these equations (or
a proof of unsatisfiability). Solvers are used for a variety of practical
applications, from VLSI verification to transportation route planning.
Recently several authors have attempted to use solvers to perform one of
the most challenging tasks in modern computer science - cryptanalysis of
symmetric block ciphers such as AES. To use a solver for cryptanalysis, we
provide it with a known plaintext, a known ciphertext and the set of
mathematical equations which use an unknown secret key to transform between
the two. The solver is then expected to output the secret key which links
the given plaintext and ciphertext, thus satisfying the equation set.
Fortunately, solvers are not currently capable of directly attacking modern
ciphers. However, the situation is drastically different when side-channel
data (information leaked from the cryptographic device due to its internal
structure) is introduced into the equation.
This talk will introduce side-channel cryptographic attacks, survey our
latest efforts in using machine solvers to attack cryptosystems, and
conclude with a successful attack on the AES cipher which requires
surprisingly little side-channel data and computation time.
Joint work with Mathieu Renauld, François-Xavier Standaert and Avishai Wool
14.30
דר' נתן קלר, אוניברסיטת בר אילן
Dissect and Conquer: New algorithms for cryptanalysis of multiple encryption, knapsacks and other combinatorial search problems
A composite problem is a problem that can be split into several
simpler subproblems which can be solved independently of each
other. A wide variety of problems in Cryptography and in other areas
of Computer Science can be treated as composite problems, including
finding the key of multiple encryption schemes with independent
subkeys, solving knapsack problems, and even finding the shortest
solution to the Rubik's cube puzzle.
The meet-in-the-middle (MITM) approach suggests
that in such problems, one can obtain the time/memory tradeoff curve TM=N
(where N is the number of possible solutions, and T, M are the time and
memory complexities of the algorithm). In the last thirty years, several
generic algorithms improved over the basic MITM approach and achieved
several points on the tradeoff curve TM=N^{3/4}. These include the
Schroeppel-Shamir algorithm for knapsacks (1984), the van Oorschot-Wiener
algorithm for multiple encryption (1996) and others. In 2010,
Becker et al. showed that TM=N^{3/4} can be obtained for most values
of M.
In this talk we show that surprisingly, the curve TM=N^{3/4} is not
optimal. We achieve a better curve of TM<N^{3/4} for any M<N^{1/4}, and in
particular, obtain TM=N^{5/7} with M=N^{1/7} in the cases of 7-encryption
and knapsaks. Our results are obtained by a new algorithm called
dissection, in which the problem is divided into several
sub-problems by guessing (parts of) intermediate values. An interesting
feature of the technique is that the best results are obtained by division
into "exotic" numbers of parts, such as 7 and 11, rather than to 2^k parts
(as was common in previous works).
Joint work with Itai Dinur, Orr Dunkelman and Adi Shamir