4
$\begingroup$

The question is about E0, the stream cipher used to secure Bluetooth communication. The impression I get is that it's more secure than A5/1. Also, why wasn't AES used instead?

$\endgroup$
9
  • 4
    $\begingroup$ what is your exact question regarding E0? $\endgroup$ Jan 17, 2018 at 7:17
  • 3
    $\begingroup$ Have you considered Yi Lu, Willi Meier and Serge Vaudenay's The conditional correlation attack: a practical attack on Bluetooth encryption, in proceedings of Crypto 2005? $\endgroup$
    – fgrieu
    Jan 17, 2018 at 11:58
  • $\begingroup$ @indiscreteLogarithm My question is about how secure it is. $\endgroup$
    – Melab
    Jan 18, 2018 at 2:15
  • $\begingroup$ @Patriot I don't think it ever has been king. Because it's designed with LFSRs, it's always been suspected to be pretty weak. Cryptographers have never thought of it as highly-regarded. $\endgroup$
    – forest
    Jan 25, 2021 at 1:04
  • 1
    $\begingroup$ @Patriot I'm aware. I just meant that A5/2 had to be created for export purposes no matter how strong or weak A5/1 was. It was simply a matter of key size. It's just that LFSRs are really efficient in hardware (back then, there's no way the anemic GSM baseband could process something secure like 3DES in real-time). There are a few decently secure(ish) designs using them like the alternating step generator, shrinking generator, and self-shrinking generator, and of course Trivium uses an NLFSR, but generally anything LFSR-based is not going to be the most secure cipher out there. $\endgroup$
    – forest
    Jan 25, 2021 at 2:42

2 Answers 2

9
$\begingroup$

Bluetooth has gone through a few transitions in protocol. Bluetooth BR/EDR uses E0/SAFER for a cipher and Bluetooth LE uses AES-CCM. Fundamentally, when you write a specification as an engineer, you are looking for a minimally viable CMOS implementation. You make choices that are not always the best from a cryptographic standpoint because you have space or power constraints. For instance, AES is rather large compared to some stream ciphers and I believe the motivation of using E0 was die space because LFSRs are smaller than an AES implementation. I personally use SIMON over AES in hardware because it's smaller, faster and lower power in a CMOS implementation, and this is particularly true when you are encoding a "bit stream", such you'll have in RFID or Bluetooth.

I know from being in a meeting that FIPS-140 validation for Bluetooth was an important conversation with the Bluetooth LE spec, which is why AES was added. I can only assume that AES was not used in the original ICs due to cost on the hardware side. Looking at 130nm dies (so, back in the day), AES would cost me about 0.03 USD in area. Just by guessing the area of E0, I would say it's 0.01 USD, so it must have mostly been an economic consideration during the time of early adoption.

E0 itself is not particularly secure and is vulnerable to known plaintext attacks.

$\endgroup$
3
  • 2
    $\begingroup$ Although this explains why E0 is used in Bluetooth, it doesn't explain how secure it is. You may want to edit your answer to mention its security (as far as I know, one-level E0 is severely vulnerable to known plaintext attacks, and two-level E0, used in 2.1 to 4.0, is slightly less vulnerable). $\endgroup$
    – forest
    Jan 6, 2019 at 11:00
  • 3
    $\begingroup$ @forest I am aware that E0 is not secure; however, I'm not really competent as a cryptographer. I'll see if I can find something. If you are knowledgeable in the shortcomings of E0 specifics, feel free to edit in a blurb or a link. $\endgroup$
    – b degnan
    Jan 6, 2019 at 18:08
  • $\begingroup$ Yes, SIMON requires less resources than AES. Even an AES-implementation with a single Sbox will require more gates and registers than SIMON. BUT this can't be the only reason for selecting SIMON instead of AES. AES is probably the most evaluated, tested and trusted block cipher. SIMON is very much less trusted (even mistrusted). $\endgroup$ Feb 11, 2020 at 11:51
2
$\begingroup$

The main reason the original Bluetooth spec didn't just use AES is simpler than the implementation complexity reason given in the earlier answer: AES just hadn't been invented when Bluetooth was designed.

The first Bluetooth specification was released in July 1999 and AES didn't complete even the downselection from fifteen to five candidates until August 1999.

It wasn't just the specification that was available before AES. Bluetooth end user products, such as the Ericsson HBH-10 headset, were shipping at the end of 2000 (maybe early 2001) about the same time the final AES algorithm selection was made (October 2000) and about a year before AES was approved as FIPS PUB 197 (November 2001).

It would not be unreasonable to guess that chips were being designed about a year before the specification was released (for interoperability testing), and taping out about a year before end products were released.

With AES unavailable, we can broaden the question to ask why they chose E0 and not something else. Without speaking to the authors, I don't think we'll get definitive answers, but we can make some guesses. (To be clear, I have no special knowledge of the decisions, I'm basing this all on information I can find with a web search today and my personal interpretation.)

It's clear the Bluetooth specification authors were aware of cryptographic work that was going on. The Bluetooth 1.1 core specification reveals this in a footnote:

The authentication function $E_1$ proposed for the Bluetooth is a computationally secure authentication code, or often called a MAC. $E_1$ uses the encryption function called SAFER+. The algorithm is an enhanced version¹ of an existing 64-bit block cipher SAFER-SK128, and it is freely available.


¹ It is presently one of the contenders for the Advanced Encryption Standard (AES) submitted by Cylink, Corp, Sunnyvale, USA

Although, as the specification notes, SAFER+ was one of the AES candidates, it didn't survive the fifteen to five downselection in 1999. Since the 1.1 specification is dated February 2001, I can only assume that the word “presently”, in the footnote I quoted, is left over from an earlier version of the specification.

It's odd that the authors were prepared to use an AES candidate for authentication but not encryption. The implementation complexity requirements for real-time operation for encryption may have been an issue. Or, maybe the specification authors did not want to choose an AES candidate for the heavy throughput of encryption as they were new, untested algorithms.

In contrast, it looks like E0 had some theoretical backing. The Bluetooth 1.1 specification says (emphasis added):

The key stream bits are generated by a method derived from the summation stream cipher generator attributable to Massey and Rueppel. The method has been thoroughly investigated, and there exist good estimates of its strength with respect to presently known methods for cryptanalysis. Although the summation generator has weaknesses that can be used in so-called correlation attacks, the high re-synchronization frequency will disrupt such attacks.

Although there were known weaknesses in the algorithm, I think it would be fair to say that the specification authors thought they knew where the weaknesses were and thought they'd avoided them.

You mentioned A5/1. By the time Bluetooth was being developed, this was already showing weaknesses. I'll quote Wikipedia's entry on A5/1 about known-plaintext attacks:

In 1997, Golic presented an attack based on solving sets of linear equations which has a time complexity of $2^{40.16}$ (the units are in terms of number of solutions of a system of linear equations which are required).

(I think the Golic paper is Cryptanalysis of Alleged A5 Stream Cipher).

For completeness, although this information would not have been available when the choice of Bluetooth encryption was being made, I will add that by 2000, A5/1 attacks had improved significantly (see the Wikipedia page for details). I think nowadays it's considered broken. For example, this 2008 report from Black Hat DC conference says:

The A5/1 encryption standard used in the EU and the US has been previously considered to be pretty secure, but research conducted by David Hulton of Pico Systems and Steve Muller from CellCrypt shows that the scheme hasn't aged well. The pair used the conference to showcase a device built for £500 which was capable of breaking the A5/1 encryption on an intercepted conversation in under thirty minutes.

Perhaps more importantly, for an algorithm to be included in the Bluetooth specification, it would need to published publicly and be made available royalty free. A5/1 was secret (Wikipedia: “Though both were initially kept secret, the general design was leaked in 1994 and the algorithms were entirely reverse engineered in 1999”).

A couple of years before Bluetooth chose E0, 802.11 chose RC4, another stream cipher but not LFSR based. The Fluhrer, Mantin and Shamir attack on RC4 hadn't been published when Bluetooth was being designed. However, RC4 also fails the requirement to be public and royalty free (Wikipedia: “RC4 was initially a trade secret, but in September 1994, a description of it was anonymously posted to the Cypherpunks mailing list. … RSA Security has never officially released the algorithm”).

The requirement for the algorithm to be royalty free for commercial use ruled out IDEA.

Blowfish was patent free but, according to that Wikipedia article, changing keys, which Bluetooth would have required to happen between packets when multiplexing links, is slow (“Each new key requires the pre-processing equivalent of encrypting about 4 kilobytes of text, which is very slow compared to other block ciphers.”, for comparison, E0 needs about 240 LFSR clock cycles to get ready).

That's not to say implementation size would not have been in issue. If so, for estimating the area cost, the appropriate single-chip CMOS process node at the time would probably have been 0.35-micron judging by these announcements from Silicon Wave (1999), and Cambridge Silicon Radio (2000).

The requirements for an algorithm to be proven, royalty free, efficient in gates and quick to start up may have narrowed the options immensely.

I've had a quick look to see if there'd been any improved attacks on E0 since the 2005 paper referred to in comments. There don't appear to have been, so I'll quote the key part of the abstract of the 2005 Lu, Meier and Vaudenay paper here to make sure it doesn't get lost:

Our best attack finds the original encryption key for two-level E0 using the first 24 bits of $2^{23.8}$ frames and with $2^{38}$ computations. This is clearly the fastest and only practical known-plaintext attack on Bluetooth encryption compared with all existing attacks.

There have been other attacks on Bluetooth since that paper, but they appear to be on implementations and inputs to the E0 algorithm, not on the core cipher.

The requirement for $2^{23.8}$ frames is quite significant given the normal Bluetooth data rates: it's technically practical but if it were possible on real-world links, I would have expected to see someone making a press release similar to the one I quoted earlier for A5/1 (for example, decrypting a Bluetooth link after thirty minutes of music streaming), or as were made for Wi-Fi's WEP when that fell.

However, $2^{23.8}$ is far too close to achievable frame collection targets to be comfortable. It's probably reasonable to assume better attacks are possible.

For BR/EDR links between devices where Secure Connections is not supported, so where E0 has to be used, the algorithm used today is identical to the one released in 1999.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.