Common Scrambling Algorithm
The Common Scrambling Algorithm (or CSA) is the encryption algorithm used in the DVB digital television broadcasting for encrypting video streams.
CSA was specified by ETSI and adopted by the DVB consortium in May 1994.
History
CSA was largely kept secret until 2002. The patent papers gave some hints, but important details, like the layout of the so-called S-boxes, remained secret. Without these free implementations of the algorithm were out of question. Initially, CSA was to remain implemented in hardware only, and this would have made it difficult to reverse engineer existing implementations.
In 2002 FreeDec was released, implementing CSA in software. Though released as binary only, disassembly revealed the missing details and allowed reimplementation of the algorithm in higher-level programming languages.
With CSA now publicly known in its entirety, cryptanalysts started looking for weaknesses.
Description of the cipher
The CSA algorithm is composed of two distinct ciphers: a block cipher and a stream cipher.
When used in encryption mode the data are first encrypted using the 64 bits block cipher in CBC mode, starting from packet end. The stream cipher is then applied from packet start.
Block cipher
The block cipher process 64 bits blocks in 56 rounds. It uses 1 byte from expanded key on each round.
Stream cipher
The first 32 round of the stream cipher are used for initialization and do not generate any output. The first 64 bits of data are used as initialization vector during this phase and are left unchanged. The stream cipher then generates 2 bits of pseudo-random stream on each round which are xored starting at bit 64 of the packet.
Weaknesses
Were CSA to be broken, encrypted DVB transmissions would be decipherable, regardless of any proprietary conditional access (CA) system used. This could seriously compromise paid digital television services, as DVB has been standardised on for digital terrestrial television in Europe and elsewhere, and is used by many satellite television providers. No attack has yet been published, however.
Cryptanalysis
Cryptanalysis is made more difficult by the fact that most data is protected both by the block and the stream cipher. However, there are parts that are protected by one of the ciphers only: The first 64-bit block is only encrypted with the block cipher, and the any excess bits after the last 64-bit block (zero to seven bytes) are protected by the stream cipher only.
As the key in current implementations is only 48 bits long, this opens up for possible known plaintext attacks when combined with knowledge of the underlying plaintext structure. For instance, as the first three bytes of the Packetized_elementary_stream PES header is known to always be 0x000001, it would be possible to launch a brute force attack. Such an attack would reveal millions of possible keys, but still few enough to make it practical to attempt decryption of other parts of the data with the same key in a second pass to recover the true key.
However, 48 bits, even if small by today's standards, is a significant amount of keyspace to search through. For most practical applications, one would want to break the key faster than it is changed, and as the key changes at a minimum of every 120 seconds, this would require scanning through on average at least half the keyspace in that period of time. As an implementation taking 1 µs for each try would require 8.9 years to scan the entire keyspace, this makes a brute force approach impractical for decrypting the data in real time, even with a highly parallel implementation.
Brute force approach
While CSA algorithm uses 64-bit keys, most of the time only 48 bits of key are unknown, since bytes 3 and 7 are used as checksum bytes in CA systems, and may be easily recalculated. This allow reducing the brute force search time.
Theoretical implementation in a FPGA that would consist of 42 hw-threads that each would test 1 key per clock-cycle. At a clock-rate of 50 MHz this would allow the key to be found in ~19 days since we would expect, on average, to find the key after 247 tries for a 248 key. The problematic part in this would be to determine when a valid key was found since that would involve checking the decrypted data for known things like MPEG-headers which could be hard to implement efficiently enough to fit in a today commercially available FPGA. One possible way to reduce the needed complexity in the FPGA could be to have a multi-layer approach where the first one just discards all keys that are known to be invalid with quite simple checks and one or more that checks for additional information.
Most CA systems use short lived keys which are replaced every few seconds, making such implementation useless until computational power increase dramatically. Moreover, the usual 48 bits key length may still be increased to 64 bits in the future to improve system strength, as this is not a limitation of the algorithm.
Software implementations and bit slicing
The stream cipher part of CSA is prone to bit slicing, a software implementation technique that allows decryption of many blocks, or the same block with many different keys, at the same time. This significantly speeds up a brute force search implemented in software, although the factor is too low to make a real-time attack practical.
The block cipher part is harder to bit slice, as the S-boxes involved are too large (8x8) to be efficiently implemented using logical operations, a prerequisite for bit slicing to be more efficient than a regular implementation. However, as all operations are on 8-bit subblocks, the algorithm can be implemented using regular SIMD, or a form of “byteslicing”. As most SIMD instruction sets, with a notable exception of AVX2, do not support parallel look-up tables, the S-box lookups are done as in a non-bytesliced implementation, but their integration into the rest of the algorithm is not hampered markedly by the byteslicing.
Both techniques are used in libdvbcsa, a free implementation of CSA.
References
- Wirt, Kai (2003). "Fault attack on the DVB Common Scrambling Algorithm (Report 2004/289)". Cryptology ePrint Archive.
{{cite journal}}: Unknown parameter|month=ignored (help)