I found a bug in Motorola DMRA ARC4

[jimmy9999]

I found a bug in Motorola DMRA ARC4 Encryption.
The bug is present in the standard, so it is found in all manufacturers who use the DMRA ARC4 standard.

The DMRA standard uses an LFSR to generate 32 hit IVs. An IV (Initialization Vector) should only be repeated after 4 billion times (2 to the power of 32) because two superframes using the same IV will be encrypted the same.

The bug is as follows:

Motorola used the following generator polynomial for the ARC4: x^32 + x^4 + x^2 + 1.

However, it is a non-primitive polynomial that generates short cycles.
IVs do not repeat every 4 billion times, but every IV 294903. That's an 18-bit IV when it's supposed to be 32-bit.

Can anyone confirm the bug?

 

[mtindor]

I found a bug in Motorola DMRA ARC4.
The bug is present in the standard, so it is found in all manufacturers who use the DMRA ARC4 standard.

The DMRA standard uses an LFSR to generate 32 hit IVs. An IV should only be repeated after 4 billion times (2 to the power of 32) because two superframes using the same IV will be encrypted the same.

The bug is as follows:

Motorola used the following generator polynomial for the ARC4: x^32 + x^4 + x^2 + 1.

However, it is a non-primitive polynomial that generates short cycles.
IVs do not repeat every 4 billion times, but every IV 294903. That's an 18-bit IV when it's supposed to be 32-bit.

Can anyone confirm the bug?

I don't know anything. But I have to ask -- how does this "bug" manifest itself? Who would be affected? What do you suspect the ramifications to be?

 

[jimmy9999]

Z

I don't know anything. But I have to ask -- how does this "bug" manifest itself? Who would be affected? What do you suspect the ramifications to be?A

ARC4 is a stream cipher in OFB Mode.
It is only secure if the IV does not repeat with the same key, otherwise the encrypted stream can be decoded without knowing the key. You can decode the encrypted stream without having to try all the possible keys (2^40 in ARC4) so decoding can be very fast.

Wikipedia explains the Initialization Vector:

Initialization vector - Wikipedia

en.wikipedia.org

Additionally for the output feedback mode (OFB mode), the IV must be unique.

This could pave the way for very quick attacks to find the key, as there was for WEP (WIFI standard) where the IV was 24 bits.

In the case of this bug, the IV is actually only 18 bits.

Wired Equivalent Privacy - Wikipedia

en.wikipedia.org

Weak security​

Because RC4 is a stream cipher, the same traffic key must never be used twice. The purpose of an IV, which is transmitted as plaintext, is to prevent any repetition, but a 24-bit IV is not long enough to ensure this on a busy network. The way the IV was used also opened WEP to a related-key attack. For a 24-bit IV, there is a 50% probability the same IV will repeat after 5,000 packets.

In 2005, a group from the U.S. Federal Bureau of Investigation gave a demonstration where they cracked a WEP-protected network in three minutes using publicly available tools.

Wikipedia explains that for 24 bits you only need to capture 5000 packets to find the key (half the size of the IV, i.e. 2 to the power of 12 bits = 4096 packets). For 18 bits, half of which is 9 bits, it would be enough to capture 2 to the power of 9, i.e. 512 superframes, to find the key with a related-key attack.

This is the Birthday Attack:

Birthday attack - Wikipedia

en.wikipedia.org

 

[jimmy9999]

If you know anything about the LFSR, you can visually see the bug by initiating the LFSR x^32 + x^4 + x^2 + 1
to 1, then you will see the short cycle visually which looks like this:

45145144
04404405
11140510
15051014
41415154
01155040
01555114
50410154
14014411
54505444
11004054
44511411
11015444
44504054
05511411
41015444
01441111
44050150
54551551
05550415
10414010
14011445
05150541

Without the bug the IV should be random like this:

B6DB68A3
CF213212
B93A9645
C28201D2
63B1D6A6

If you initialize the LFSR with values other than 1 you won't see the bug visually, which may explain why no one has ever found this bug until now.

 

[mtindor]

I don't know anything about anything. I'll take your word for it.

 

[Whiskey3JMC]

Oh how I get lost perusing some of these threads...

 

[jimmy9999]

Anyone have names of encryption specialists on this forum so we can ask them to confirm?

 

[KevinC]

If the "bug" is present on the DMRA ARC4 standard I see no reason to not see it in any implementation. Probably why MSI chose to call it "privacy".

 

[jimmy9999]

If the "bug" is present on the DMRA ARC4 standard I see no reason to not see it in any implementation. Probably why MSI chose to call it "privacy".

yes it's everywhere so anyone will be able to test what I've found as long as they have a DMRA RC4 compatible radio.

What do you mean by the sentence "MSI chose to call it privacy"?

 

[EI9BAB]

The theoretical flaw around re-using IVs is that if you use the same key and repeat the IV at some point then you will have the same keystream for two superframes. Even then you would have to XOR the two resultant superframes and try to determine the two underlying transmissions from that and that only gives you 360 milliseconds of voice. Alternatively, if you want to do a real-time pre-calculated attack on the keyspace then you could calculate all the keys for a specific IV in advance so the quicker that rolls round then the less secure your algorithm becomes.

However, I think you would need over 65 days of continuous audio from a single radio before you you start to recycle IVs. Even with theoretically unlimited unrepeating IVs you are far more likely to encounter this problem with multiple radios on the same system as you will get the same IV being coincidentally used by other radios before you will encounter one radio repeating them itself.

It may be that this IV calculation was selected for a reason as some IVs are weaker than others or maybe they need to be guaranteed to be spaced a certain distance apart? It still feels like a practical IV generation solution and not necessarily a vulnerability.
The original FMS WEP IV attack is different as it lies in generating large volumes of messages in conjunction with weak IVs to determine certain bits of the keystream. In fact increasing the potential number of IVs might make thsi attack easier rather than harder. Anyway, that is not the most practical attacke on EP/RC4 although the RC4 algorithm is inheritently insecure and there are much bigger vulnerabilites outside potential IV re-use that make Enhanced Privacy insecure allowing it to be cracked with only one IV required. (Hence the comment above as it is marketed as enhanced privacy as opposed to "secure".)

 

[TDR-94]

Privacy and security are not one in the same. MSI used the term Privacy Plus because ARC4 was never meant to used as as a "secure" option. It's a weaker encryption algorithm by design, to be used as a cost effective option. It's primary purpose it to prevent scanners from monitoring the talkgroup traffic. Many proprietary digital modes were once marketed as options for private communications, as a less expensive and complicated option, at the time, to securing radio traffic with encryption algorithms. These were considered good enough to prevent scanners from monitoring the traffic and making it private but not necessarily "secured" from being monitored.

And yes nothing is, by definition, truly secure. The point is to make it so difficult that it's not worth the expense and time required to obtain the data or information, when it pertains to communications traffic.

 

[jimmy9999]

However, I think you would need over 65 days of continuous audio from a single radio before you you start to recycle IVs

You're right if the IV is indeed 32 bits, but with the bug I found the IV is now only 18 bits (and 9 bits with the birthday attack) and it is only necessary to capture 512 superframes before repeating the IV.

512*360 ms = 184,320 ms = 184 seconds of audio stream to be captured.

A big difference between the theoretical 65 years and 184 seconds, right?

 

[slicerwizard]

OMG. Time for some hard facts.

Subscriber radios frequently reuse IVs. Their "random initial IV" generators are trash. Often, duplicate IVs can be seen in back to back voice calls. This alone would make this "discovery" pointless. Further, DMR EP encryption and P25 ADP encryption use tiny 40 bit keys. The resultant keyspace is so small that finding further flaws is rather pointless. EP and ADP keys can be derived from a single random voice superframe (180 ms of audio). Don't believe me? Record a few seconds from the middle of an EP or ADP transmission and I'll pull out the key. Raw source audio WAV recordings from DSD+ work best for me. And don't be getting the wrong idea - I'm not running a key cracking service for anyone - but I'll be happy to prove my claims.

 

[jimmy9999]

Rather than trying to decrypt frames, can't you explain what is the process that retrieves a 40-bit key from a single superframe?

EP and ADP keys can be derived from a single random voice superframe (180 ms of audio).

 

[slicerwizard]

Rather than trying to decrypt frames, can't you explain what is the process that retrieves a 40-bit key from a single superframe?

What part of I'm not running a key cracking service for anyone was unclear?

 

[jimmy9999]

What part of I'm not running a key cracking service for anyone was unclear?

A key cracking service cracks the keys for someone else.
An explanation of the process is not a key cracking service, but a technical explanation of its own claims.
Just like I did myself with the bug I found.

For example, Fluhrer, Mantin, and Shamir explained the flaws in RC4 and it was not a ke cracking service:

rc4.dvi

Because if you're a cloud server administrator, you could crack a 40-bit key quickly using all your servers. That would be brute force and it wouldn't prove what you're saying.

I'm talking about bugs that allow you to find the key without brute force.

When you write:

EP and ADP keys can be derived from a single random voice superframe (180 ms of audio).

This implies that you can find the key without brute force just by deducting the key from the superframe.

 

[mastr]

A key cracking service cracks the keys for someone else.
An explanation of the process is not a key cracking service, but a technical explanation of its own claims.
Just like I did myself with the bug I found.

Thank you for saving me the keystrokes.

 

[snoopyII]

This might be a useful discussion to some, but on this platform its a very, very small group of people. This is way above 99% of the people who use this forum. I'll take your word for it, that there may be a bug. Looking for someone here to confirm it? You would be far better off looking for another forum that specifically deals in things like this.

ARC4 was never intended on being "secure". It serves it's intended purpose to this day. A simple cost effective way to keep radio traffic from anybody with a scanner. Cops aren't passing national secrets here. They are just trying to stay one step ahead of everyone else, especially in today's social climate.

 

[slicerwizard]

I'm talking about bugs that allow you to find the key without brute force.

You're talking about how you can pick the lock on the door in only five minutes when the window beside it is propped wide open. I see no value in it.

This implies that you can find the key without brute force just by deducting the key from the superframe.

My words carry no such implication.

 

[EI9BAB]

You're right if the IV is indeed 32 bits, but with the bug I found the IV is now only 18 bits (and 9 bits with the birthday attack) and it is only necessary to capture 512 superframes before repeating the IV.

512*360 ms = 184,320 ms = 184 seconds of audio stream to be captured.

A big difference between the theoretical 65 years and 184 seconds, right?

I'm not sure if the birthday attack applies in this situation and even if it did then it may only bring you from 2^18 to 2^17 but I could be wrong.

However, as stated earlier, this does not automatically give you the key, it just slightly compromises the keystream. If i have you two XORed messages now and you had no idea what the plaintext was for either then you wouldn't gain that much information. And (A)RC4 is much more straightforward to crack with other methods as we keep saying.