fpgaminer 5 years ago

I recently learned about side channel attacks on ChaCha20, and all other ARX ciphers.

ChaCha20 and its kin are of course resistant to timing side channels by their nature. Without thinking about it I had assumed they would resist other forms of side channel too (cache, power, EM, etc). ChaCha20 performs the exact same operations every time, regardless of its inputs. And the mixing should eventually lead to an even mixture of flip-flopping towards the middle of the cipher. So, how could it be exposed to any side channel?

Well apparently it's still weak to power (and EM by proxy) analysis: https://eprint.iacr.org/2017/1021

I haven't had the time or inclination to study the paper in depth. But if understood it correctly, the very act of accessing memory exposes the data being accessed. Even if the power difference between accessing, say 0xaf and 0x30 is so infinitesimal, it's apparently enough to correlate with power analysis and crack keys.

Quite amazing.

  • colmmacc 5 years ago

    It can be easy to forget because we all sort of mentally accept it, but ChaCha20 is length preserving, and so is trivially vulnerable to by far the simplest network side channel: size based traffic analysis. AES-GCM is too, in the same way, but AES-CBC was actually a /little/ better because it's padded to the nearest block which provides a small measure of length hiding.

    Imagine you're a state authority who wants to know who is looking at what on the internet. It's pretty easy to fingerprint websites and webpages by size; the pattern of HTML, images, video, and CSS, is highly unique. There are published papers doing this against Google Maps tiles, and Netflix movies. It's very very practical. It's utterly feasible for authorities to build these fingerprint DBs, and to fingerprint any traffic they have visibility of.

rohan1024 5 years ago

Okay I'm feeling left out here. I've no idea what this is. Can anyone please explain what is this and what is its use?

  • edelans 5 years ago

    For those wondering what is a side-channel attack : here is a definition from Wikipedia :

    In computer security, a side-channel attack is any attack based on information gained from the implementation of a computer system, rather than weaknesses in the implemented algorithm itself (e.g. cryptanalysis and software bugs). Timing information, power consumption, electromagnetic leaks or even sound can provide an extra source of information, which can be exploited.

    https://en.wikipedia.org/wiki/Side-channel_attack

    • DrPhish 5 years ago

      The easiest to understand example of this is bypassing a naive login prompt:

      If the function to test a password that has been entered stops as soon as there is a wrong character, it's trivial to write a program to send it a modified password each run and see how long it takes to come back. If it takes slightly longer than last time, then you have one more character correct. Iterate until you have the complete password.

      It's one cheesy thing that Hollywood does that at least worked at some point in the past, ie. the hacker that uses a program to crack a password one character at a time (preferably as the clock ticks down to some impending disaster)

      • jolmg 5 years ago

        Sorry for my skepticism, but even in old systems, wouldn't such a time would be too small to measure even by a program on the same computer? and I imagine that having a preemptive scheduler makes things even more complicated.

        It's hard to imagine the attack you describe being viable.

        • mmozeiko 5 years ago

          You'll be surprised, but yes - it can be measured. Not even on same computer, but across different computers on Internet, even with all the random latency in the middle.

          The idea is that you don't measure only once. You measure thousands, tens of thousands of times and more. Then any difference however small it will be also multiplied thousand times and it will be possible to measure it. Even if you will have other random processes such as OS scheduler, network latency, etc - it will be pretty obvious after thousands of measurements which ones to ignore. For example, check the histogram graphs in this paper: https://mlq.me/download/netspectre.pdf

        • teej 5 years ago

          My understanding of timing attacks is that they can be used when you can trigger the code path thousands of times quickly. This gives you execution time averages and distributions. Also, they're typically used against cryptographic hash functions which are more expensive than just a string compare.

          https://en.wikipedia.org/wiki/Timing_attack

          • jolmg 5 years ago

            But if you use cryptographic hash functions, then you can't do the timing attack described because any one character change changes the whole hash.

            • Nursie 5 years ago

              Not for cracking a password perhaps, but imagine you have a system that looks at a MAC'd ciphertext. You want the system to attempt to decrypt a malicious ciphertext you've generated, but it won't until you have passed its MAC check.

              With a timing attack, you can iterate the bytes of the MAC, itself probably based on a cryptographic hash like HMAC(sha256), until you get something that gets to the second stage.

              You reduce MAC-forging complexity from 2 to the power of the number of MAC bits, to 256 times the number of bytes in the MAC.

            • saagarjha 5 years ago

              Yup, that's why this attack doesn't really work on hash functions.

        • xenadu02 5 years ago

          > It's hard to imagine the attack you describe being viable.

          This has been the conventional thinking of software engineers for the past few decades. It turns out to be completely wrong.

          I mean who would have thought measuring memory access latency could turn speculation into an arbitrary kernel read gadget yet here we are.

    • pault 5 years ago

      I once worked with a security researcher that would use infrared lasers to measure the temperature of different parts of a microcontroller to reverse engineer it. I have no idea what he did with that information but it blew my mind at the time.

  • huehehue 5 years ago

    With the definition from edelans, attacks can be made on Ledger devices (or any device, for that matter) by watching how the hardware behaves as it does its thing.

    Here's a recent proof of concept: https://www.coindesk.com/security-researchers-break-ledger-w.... TLDR, entering your pin # on a device results in significant enough current changes that they can be picked up, turned into a training set, and your pin can be worked out.

    This repo provides a bunch of utils and examples to facilitate the testing and analysis of such attacks.

nabnob 5 years ago

Wow, this is the first time I've heard of side channel analysis and I'm super impressed by the creativity involved in these attacks.

Based on reading a couple wikipedia articles, is it correct to say that most of these attacks require access to the device that you're trying to crack?

  • fpgaminer 5 years ago

    > is it correct to say that most of these attacks require access to the device that you're trying to crack?

    Some, yes. A classic example of a side channel attack that doesn't require physical access:

    An authentication server which naively compares passwords (or even their hashes). Say they just `if (request.password != expected_password) return Error.403`. This type of naive comparison which will use memcmp or something similar creates a timing side channel. This happens because it compares the passwords one byte at a time, and returns early as soon as it finds a mismatched byte. So the length of time the server spends authenticating the passwords is dependent on how many bytes the passwords have in common. i.e. "password" != "deadbeef" takes 1 comparison, whereas "password" != "peadbeef" takes 2 comparisons.

    So an attacker can submit 256 requests to the server, cycling through every possible first byte. Whichever request takes the longest tells the attacker what the first byte of the password is. So they fix the first byte, and then repeat 256 times for the second password. And so forth until the password is cracked.

    This takes only O(N) time to crack, where N is the length of the password.

    Though this is a simple example, it ends up being a very common attack vector. And as noted, this can be performed remotely.

    (In practice things are a bit more complicated, but make attacks like this no less of a threat. You first need to determine the password length (easy, same timing side channel). And then you probably need to submit several times more requests per password attempt so you can average out the "noise" of request times. Rate limiting, etc ameliorate attacks, but are no excuse for not using constant-time algorithms.)

hart_russell 5 years ago

Is this an attack that can be mitigated by a firmware update?

  • anfractuosity 5 years ago

    https://en.wikipedia.org/wiki/Side-channel_attack#Countermea... might be of interest especially this part:

    "In the case of timing attacks against targets whose computation times are quantized into discrete clock cycle counts, an effective countermeasure against is to design the software to be isochronous, that is to run in an exactly constant amount of time, independently of secret values. This makes timing attacks impossible.[14] Such countermeasures can be difficult to implement in practice, since even individual instructions can have variable timing on some CPUs."

  • pietjepuk88 5 years ago

    > Lascar stands for Ledger’s Advanced Side Channel Analysis Repository. Its goal is to gather and provide common tools and techniques used in the field of Side Channel Analysis, within an open, customizable library.

    It's not an attack. It's just something that the Ledger security team has been working on.