안녕하세요 FDTC 및 CHES 2014

P1040275
I recently attended two of the largest workshops about hardware security: FDTC and CHES in Busan, South Korea. As usual, lots of new results were presented there.
During the Fault Diagnosis and Tolerance in Cryptography workshop (FDTC), three presentations, including the invited speaker, were about different ways to attack Pairing Cryptography algorithms with fault and side-channel attacks. This indicates that focus has moved to this cryptographic primitive and the security of its hardware implementations. Two papers presented fault attacks against the Miller algorithm which is used to compute pairings. One of these paper showed that combining an initial fault in the Miller algorithm with a second fault to bypass the final exponentiation of a pairing was possible on their target device, a AVR XMEGA-A1 microcontroller.
Two different glitch attacks were presented against microcontrollers. One of them showed that heating the microcontroller helped to induce further effects when clock glitching. In the second paper, a combination of clock glitching and underpowering were applied on both ARM Cortex-M0 and a Atmel ATxmega 256 microcontrollers. The faults obtained were skipped or duplicate instruction executions as well as wrong calculations.
New fault attacks were presented against GOST, SIMON, SPECK, Feistel and Substitution-Permutation networks. Aside from attacks, a new countermeasure was presented to protect RSA implementations against multiple fault injections. The authors made a large effort to formalize fault injections as well as showing equivalence of some fault models. They then showed how to build provable secure countermeasure against high-order fault attacks (multiple faults) with a generic fault model. This may provide a good tool for hardware designers.

P1040192 During the Workshop on Cryptographic Hardware and Embedded Systems (CHES), the best paper award was given to a team from Tohoku and Kobe. They showed that it is possible to build a detector inside a circuit with standard cells that detects if an electromagnetic (EM) probe is near the die. Usually, we use EM probes to either perform leakage acquisitions for side channel analysis or to inject localized faults using local electromagnetic radiations. If a chipset is equipped with such detector it may hinder such attacks. Their detector was implemented and tested within an AES processor. A video of their experiment was shown during the rump session.
Another team showed that a hardware Trojan construction presented last year which consists in modifying the dopant level of a gate into a circuit, can be detected when the circuit is analyzed with a FIB or a SEM.

P1040194
A presentation leading to a nice demo (picture on the right) was given by people from Tel-Aviv University and Technion. Their idea was to extract the secret key used during GnuPG encryption only by touching the chassis of a laptop. They successfully demonstrated proof of their attack on stage.
New fault attacks were also presented. A team demonstrated that the countermeasure for AES which was defeated last year has other weaknesses and they proposed a different countermeasure. Another team combined fault attacks with side channel information to attack the AES key scheduler. Meanwhile, they solved an interesting previous open question about the Hamming weight of the key scheduler. They showed that two different keys can have the same key expansion Hamming weight. They provided an algorithm to construct such keys. A side channel analysis of prime number generation was presented by ANSSI. They attacked the prime sieving algorithm before the Miller-Rabin’s tests during the prime number generation. They applied their attack on a smartcard implementation.
An interesting presentation was made about Photonic Emission Analysis (PEA). A team from Berlin performed an analysis of an arbiter-based Physically Unclonable Function (PUF), which is a common construction of timing-based PUFs. The photonic emission principle is simple. Each CMOS transistor can emit photons during a switch of its state. These photons can be observed from the backside of the chips and thus give information about the physical location of the active part of the die. This team implemented its PUF on an Altera MAX V board. For the photonic emission analysis they used a Si-CCD camera and an InGaAs avalanche diode to provide both spatial and timing resolution. With their setup they obtained the timing of some reference challenges and then these timings were used to predict further PUF outputs of given challenges and finally clone the PUF.
To sum up, more and more complex and combined attacks are being realized and the theory behind them is becoming more fully understood. This progression is resulting in hardware attacks which are practical and sometimes devastating to the security of certain products. Links are are being made between previously separate domains to achieve practical attacks. I saw lot of amazing presentations and I had really nice discussions there. I hope to see you next year in Saint-Malo.

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Forum EPFL 2014 Crypto Challenge

For the Forum EPFL 2014 job fair, we created a crypto challenge—in the spirit of CTF hacking contests—and offered to award a quadcopter drone to the first student to solve it and Bus Pirate devices to the next 2nd to 10th.

After about 10 days, no one solved it, although the difficulty was well below that of a competitive crypto challenge at (say) DEFCON qualifications.

Given the password-protected ZIP archive https://www.kudelskisecurity.com/kschallenge.zip, a first step was to recover the password: 1234. OK, next step:

The ZIP archive contained:

  • a text file named ciphertext and containing the string “407747220c5f2754c6fd192502c8f597814bc95ce897eb6a3c45ba4a7150fe86d054d1607e94bf0fc90790ddba8925b50c8c6159b091651442779e86febfc6b1bd736d77d28d89d96ebee2d4038f26cb77a1b843afdb1c7bf3c01518a77b6f87d25b8071cafbfc30ee3f569f72342dcc” (224 characters, thus 112 bytes); one was supposed to deduce that this was the hexadecimal representation of a ciphertext (encrypted message).
  • a command-line Python script named challenge.py, taking as parameter a file name and encrypting the file with CBC-AES-128 (from Python’s Crypto.Cipher module) using a key generated by a custom PRNG. The script is copied below:

#!/usr/bin/env python

# Copyright (c) 2014 Nagravision SA, all rights reserved

import os
import sys
import hashlib
from Crypto.Cipher import AES

ZEROBLOCK = '\x00'*16

def encrypt(key, iv, plaintext):
    assert len(key) == 16, 'key isnt 16-byte'
    assert len(iv) == 16, 'iv isnt 16-byte'
    assert len(plaintext) % 16 == 0, 'plaintext length isnt multiple of 16'
    cipher = AES.new(key, AES.MODE_CBC, iv)
    return cipher.encrypt(plaintext)


def xor(xs, ys):
    return ''.join(chr(ord(x) ^ ord(y)) for x, y in zip(xs, ys))


class PRNG(object):

    def __init__(self):
        self.state_bytes = 64
        self.key = ZEROBLOCK
        self.iv = ZEROBLOCK
        # get low-entropy string from the environment
        entropy = ''.join(os.listdir('/proc'))
        # hash to make a higher-entropy string
        seed = int(hashlib.sha256(entropy).hexdigest(), 16)
        # ensure distinct processes have distinct seeds
        pid = os.getpid()
        new_seed = self.__diversify(pid) * seed
        # hash again to get a 32-byte string
        final_seed = hashlib.sha256(str(new_seed)).digest()
        # initialize state
        self.state = final_seed + '\x00'*(self.state_bytes - len(final_seed))
        # fill state with pseudorandom bytes
        # + proof-of-work, against bruteforce
        for i in range(10000):
            self.__update()

    def __print_state(self):
        print self.state.encode('hex')

    def __diversify(self, x):
        return pow(3, x, 65537) & 0xffff

    def __update(self):
        mask = encrypt(self.key, self.iv, self.state)
        self.state = xor(mask, self.state)

    def get_bytes(self, nbbytes):
        randbytes = self.state[-nbbytes:]
        self.__update()
        return randbytes


def main():
    prng = PRNG()
    plaintext = open(sys.argv[1]).read()
    key = prng.get_bytes(16)
    iv = ZEROBLOCK
    ciphertext = encrypt(key, iv, plaintext)
    print ciphertext.encode('hex')

if __name__ == '__main__':
    main()

The PRNG is seeded with

  • a snapshot of the content of /proc, which is highly unpredictable on a typical Linux system.
  • the “diversified” PID, which on a Linux system ranges from 1 (init) up to 32768 (see /proc/sys/kernel/pid_max)

These two elements are then multiplied together on the line new_seed = self.__diversify(pid) * seed. Reminder: for all x, we have x×0=0.

In the above PRNG, one can observe a function __diversify(), which doesn’t seem to add entropy, let alone to “diversify” the PID, but rather to deterministically map a PID x to the value (3x mod 65537) mod 65536, since the AND mask 0xffff is equivalent to a reduction modulo 1+0xffff. Now, observe that pow(3, 32768, 65537) equals 65536, which is equivalent to 0 modulo 65536.

Bottom line: there is a PID, namely 32768, for which the key does not depend on the highly unpredictable content of /proc. With this PID, one obtained the key “622c4f56d20f0825e22751e0f29b38f5″. One could then decrypt the ciphertext, and notice that it looked like a gzip’d file stripped of its first bytes (1f 8b 08 08). The rest is left as an exercise :-)

How DNS kills the Internet

There is a huge amount of Internet traffic just for Domain Name System DNS, as the amount of domain names grows it also becomes more complex. Due to the architecture of DNS, more complex means also increased time upon name resolution. This article tries to show why it happens and to give suggestions to improve it. Most of the points have been previously exposed (e.g. Notes on the Domain Name System, RFCs, …). We try to give a clear view of the whole state of DNS and show some statistics of our measurements.

How DNS works

To simplify, this article focuses mainly on domain name to IPv4 address resolution (A records). DNS provides resolution in a hierarchical distributed way. The following image illustrates the domain name resolve mechanism (credits to wikimedia.org).

An_example_of_theoretical_DNS_recursion

Basically there are 13 root name servers (there are 13 IP addresses but there are hundreds of root servers distributed all over the world using Anycast addressing). Root servers serve the “.” domain; all domain names end with “.”, and if it is omitted a suffix is added. If it is a public Internet domain name, the suffix will usually be “.”. Root servers don’t have the A record for the requested domain name, except for the TLDs name servers themselves, but they delegate to the Top Level Domain (TLD) name server. Basically they respond I don’t know, but these servers may know (illustrated above by Try 204.74.112.1). The mechanism is the same for the TLD name servers until it reaches the name server that has the answer (completed in 3 queries in the picture).

Continue reading

RIPE what they sow

tl;dr looking for internet resources information ? Go for RIPEStat, an interface to RIS (Routing Information Service), which allows you to retrieve very interesting and accurate information regarding BGP/AS/Routing/prefixes/… – it all happens here.

Ever wanted to know the evolution of internet routing paths, or maybe a country’s internet resources, or even the different paths leading to your IP address ?

Well, RIPE is collecting a ton of information through their RIS (Routing Information Service). In short, they have probes spread all around the world that retrieve information regarding internet resources (routing, BGP, geolocation, …). It is possible to query those probes (and the resulting data) through the RIPEStat interface. A service providing raw json query (through HTTPS GET query) is available but also some nice widgets to get the information you’re looking for.

I won’t go into details for all available resources, as they are well documented on RIPE’s API page, but note that some of them could be interesting for someone looking for specific data/answers on the current (or past) situation of some specific internet resources.

The basic available resources that might be quite useful for an everyday network professional include:

  • Abuse Contact Finder - allows you to query whois entry for abuse contact by providing either a prefix, a single IP address or an ASN
  • Blacklist - allows you to know if a specific prefix or IP range is UCEPROTECT-blacklisted (I wouldn’t rely on them too much though ;-))
  • Geolocation - if you want geo coordinates of a prefix, IP range, ASN or even hostname
  • Network Info - provides you the prefix and the ASN to which the queried IP belongs to
  • Reverse DNS IP - simple reverse DNS lookup of an IP address
  • Whats My Ip - the usual what-is-my-ip query
  • Whois - a whois lookup on a specific resource (IPv4, IPv6 or ASN)

Continue reading

SHA-1 backdooring and exploitation

This content was originally published on the website of the Malicious SHA-1 project.

Summary

This is about the Malicious SHA-1 project, a research project that demonstrates how the security of the SHA-1 hashing standard can be fully compromised if one slightly tweaks some of the predefined constants in the SHA-1 algorithm. That is, we show that systems using “custom” versions of SHA-1 may include backdoors exploitable by the designers. Such custom versions of cryptographic standards are typically found in proprietary systems as a way to personalize the cryptography for a given customer, while retaining the security guarantees of the original algorithm.

The colliding messages constructed can be valid archives files (RAR or 7zip) such that the content of the two archives can be fully controlled. We also build colliding JPEG files, which can be any two images, as in the example below (images were chosen at random):


Continue reading

Power analysis basics

 0. PREFACE

Recently I gave a two-hour workshop about power attacks at PHDays conference. After the workshop, I understood that two hours are not enough to present and explain power attacks to people who never worked with Side Channel Analysis before. Luckily, I was invited to give a 4-hour workshop at ZeroNights, so I would like to make a series of posts to explain power analysis attacks in a better way and then use these posts (and, hopefully, comments) to improve my workshop at the forthcoming conference. I will try to make high-level yet detailed enough explanations, otherwise the workshop may require more time.

1. INTRODUCTION

Power attacks is a group of Side Channel Attacks that analyze devices’ power consumption to:

  • extract binary data; for example, secret keys of cryptographic algorithms;
  • understand timing of a particular operation;
  • dump the opcode values (Side Channel Based Reverse Engineering.

This looks unrealistic but statistical methods applied in Side Channels can distinguish a bit switch 1 to 0 from a bit switch 0 to 1. Since these operations can be distinguished, an attacker can extract processed binary data and get confidential information.

This post explains the very basics of power attacks, namely, when digital circuit consumes power, how power consumption can be modeled and thus used to reveal algorithms’ data. At the end of the post I will explain how power traces measured during DES execution can be analyzed to get the correct 6 bits of a DES round key. Some of the Side Channel Attack properties were discussed in the previous post ‘Timing attacks – Part 1′, so I encourage you to read that post first. Continue reading

PHDays @ Moscow

In May I attended Positive Hack Days, a.k.a. PHDays, in Moscow. This is one of the three largest security events taking place in Russia. PHDays included a conference, Capture the Flag competition, workshops, hands-on activities, roundtables, investment proposal presentations, etc. Attendees from different countries and various security domains presented their results and shared their knowledge with approximately 2,000 visitors (the event was taking place during two days). In this post I would like to highlight several observations and insights that could be of interest to you.

phd_logo_black

The video of all the talks can be found here and presentations here.

The talks were given in parallel at four different halls, so I could not attend all of them. From the talks I saw I would like to select the following presentations for a mention in this post:

- Smart TV Insecurity by Donato Ferrante and Luigi Auiremma. The presentation showed that an attacker can have root access or dump the entire application code of modern TVs.
- My Journey Into 0-Day Binary Vulnerability Discovery in 2014 by Alice Schevchenko. I was pleasantly surprised. Twice. Firstly, I was surprised to discover Alice’s business acumen and her personality, since I have not met many women in the reverse engineering and fuzzing software field who are founders of their own companies. Secondly, I was surprised by the fact that there are plenty of 0-day vulnerabilities in binaries even in the latest software from the biggest companies.

Continue reading