P25 cryptography security video - RUXCON 2011

[ElroyJetson]

It's interesting that the very nature of IMBE family based codecs actually makes the task of breaking encryption a great deal easier, at least in theory.

The known silence attack is workable. Not cheap in computing power terms, but workable.

Any codec that works like IMBE, that is, there is a finite list of sound symbols that exist and all speech is comprised of the symbols that are "best fit" to the original audio, and then sent to encryption, produces a relatively limited range of possible output data as compared to, say, direct linear PCM encoded audio going into the same encryption scheme.

I don't know the actual numbers, but presume for a moment that the latest version of IMBE audio has 2400 "building blocks" from which all audio is synthesized. That's a lot of blocks to correlate but it's a lot less than direct encryption of analog audio after being sampled via linear PCM.

Take that to extremes in a theoretical sense. Say that you have a codec that only outputs TWO possible data values. Then encrypt that output. It'll be blatantly obvious by looking at the encrypted output that there are only two values encrypted. What the specific data strings of those output values are does not matter. What matters is that you can differentiate them. Try a billion different encryption keys and the output will STILL consist of two clearly differentiated values, and no more and no less.

You may not HAVE to fully decrypt. In some cases, you only have to figure out the patterns in the output that repeat. Then you can start correlating the different output data strings to such things as common human speech patterns. Given a long enough sample time, you should be able to know what's being said by processing the output even WITHOUT having the decryption key.

 

[Forts]

This ADP encryption doesn't require a super computer to break. However what is needed is some type of black hat software which can emulate the logic in the cipher as well as software to do the search of the 1 Trillion (not so big a number nowadays) or so keys in it and check them against the standard moment of silence which all P25 radios have at the end of their transmissions. It amazes me to no end how some hacker has not stepped up to the plate and put such a program out there in the wild so to speak.

I understand what you are saying, but why would someone put something like that out in the wild?? For starters there are huge legal ramifications, not to mention anyone using a hacked algorithm would migrate to something more secure. There is no upside to what you are suggesting.

 

[slicerwizard]

It amazes me to no end how some hacker has not stepped up to the plate and put such a program out there in the wild so to speak.

Perhaps the hackers smart enough to create ADP crackers are smart enough to understand that discreet is elite. Why would they give their local PS agencies a reason to upgrade to AES?

It's interesting that the very nature of IMBE family based codecs actually makes the task of breaking encryption a great deal easier, at least in theory.

The known silence attack is workable. Not cheap in computing power terms, but workable.

That depends entirely on the encryption key size. Anything under oh, about 50 bits, is home PC territory.

Any codec that works like IMBE, that is, there is a finite list of sound symbols that exist and all speech is comprised of the symbols that are "best fit" to the original audio, and then sent to encryption, produces a relatively limited range of possible output data as compared to, say, direct linear PCM encoded audio going into the same encryption scheme.

I don't know the actual numbers, but presume for a moment that the latest version of IMBE audio has 2400 "building blocks" from which all audio is synthesized. That's a lot of blocks to correlate but it's a lot less than direct encryption of analog audio after being sampled via linear PCM.

Except IMBE and AMBE don't use a list of sound symbols. You're thinking of older voice encoding schemes.

Take that to extremes in a theoretical sense. Say that you have a codec that only outputs TWO possible data values. Then encrypt that output. It'll be blatantly obvious by looking at the encrypted output that there are only two values encrypted. What the specific data strings of those output values are does not matter. What matters is that you can differentiate them. Try a billion different encryption keys and the output will STILL consist of two clearly differentiated values, and no more and no less.

You may not HAVE to fully decrypt. In some cases, you only have to figure out the patterns in the output that repeat. Then you can start correlating the different output data strings to such things as common human speech patterns. Given a long enough sample time, you should be able to know what's being said by processing the output even WITHOUT having the decryption key.

Aaaand that all goes out the window thanks to the 64 bit salt/MI value that changes every 360ms...

 

[balibago]

Mr sliicerwizard I personally don't think they will go to AES because they are doing this ADP encryption on the cheap. As we all know it's a felony to defeat any encryption scheme so it would be very self incriminating to put a feed out on the net for that agency. Next, most scanner users also want to monitor on the cheap so that locks out all but a few technically savvy people from listening in. Me personally I doubt these agencies will go through the trouble of replacing all this equipment just to stop a few nutty eavesdroppers. Where is wikileaks when we need them?

 

[slicerwizard]

Ok, so let's say some hacker creates an ADP cracker - what's in it for him to release it for anyone and everyone to use?

So that his ADP-using PS agencies, who thought their comms were 100% secure, but then learn that anyone with a free app off the Internet can crack their encryption keys, will go back to using workstations and cellphones for sensitive traffic? So that the next local agency, that was planning on going with ADP, will smarten up and choose AES instead?

That's his motivation?


I get that everyone would love to have ADP, DES and AES crackers just handed to them, but it looks like those who have the technology aren't in a sharing mood, which is hardly surprising.

Having said that, I wouldn't be that surprised if someone did release something somewhere down the road. That's just how these things seem to go. Hopefully, it won't be any time soon.

 

[MattSR]

Aaaand that all goes out the window thanks to the 64 bit salt/MI value that changes every 360ms...

Absolutely - just a very slight correction though, the P25 IV/MI is slightly larger at 72 bits in size.

 

[slicerwizard]

The last eight bits of the field are always zero and not used, so it's effectively a 64 bit value.

 

[MattSR]

Ah, yes - you're correct, my bad. You've jogged my memory - I recall the discrepancy between the field size and the actual bits in use however I could never find a reason for it in my travels...

 

[pepsima1]

P25 DES-OFB Encryption

DES/OFB only ever uses encryption operations
Top bar is keystream – the first block is created by encrypting the IV (MI) then the output is encrypted again and again
This chaining mode is preferred in wireless systems because single bit errors do not cause an avalanche
The LSD is “unknown” – which means we have to treat all 2^16 partial matches as candidate keys and repeat to see if we get DES block 15
In practice the LSD assumes a known value because Motorola has a patent that relies on setting it to a known value

If we have a known plaintext in the voice codeword then it reveals some part of the keystream
In this example two known voice codewords reveal 3 iterations of DES/OFB giving us and input block and its corresponding output block
Although the LSD is unknown we can simply take a candidate that matches and perform one more encryption to verify it for sure

 

[pepsima1]

TMTO – time/memory trade off
Best-known approach Rainbow Table
Builds a reverse index from a known value encrypted under every possible key to the key used to encrypt

DesChall code
BitSlice Approach
Matthew Kwan
50 million keys/s
40 i7 years – EXHAUASTIVE
AVERAGE IS HALF that
Scales with CPUs available
64 Opteron dual cores
310 Xeon dual cores

FPGA
Graphic shows the UCL core (as used in COPACOBANA) in a simulator – we validated it taking around 220ns per key at 100MHz.
5-6% of silicon on FPGA
Space needed for control logic overhead so 15x
100-130 million keys/s or 2.6 FPGA years

Faster on Pico E16 – claimed 1.43 years = cost 1400 USD
Pico has a product which can search keyspace in 2 days – at a cost of 90K USD

GPU
Not tried with DES but a good bitsliced implementation would be ideal
Works best when you have lots (> 768) threads with low memory usage
Would like to generate s-boxes to meet constraints: low register usage, low shared memory usage
Scales from 6x 8 core multiprocessor on MacBook Pro to 48x 8 cores on Tesla (Fermi is better still)

 

[poltergeisty]

Security Researchers Crack APCO P25 Encryption - Slashdot