Understanding CSA

[cayoenrique]

Ok, before we start posting OpenCL. We need to understand: What is CSA? Encryption & Decryption Process. How to attack it.

Be ware that for most that 20 years many people had study CSA. The results is that NO ONE has found a practical solution. In general we end up with CUDABISS witch I do not know who the author was, the well known Colibri RBT and for those that have no Accelerator well the use cwfinder witch try to speed up on CPU by using attack list of common known cws. For most of that 20 year history, finding a key via brute-force required days if not month. I been surprise that in the last years we advance to 1 day.

Now the 1 day advance is only possible because we have better technology. But Still after 20 years no one had made advances. I say this because at least 1 user here believe that we can make that change. I only hope he is right. But the rest of us know that will be harder.

Now I am here because I was contacted by Me2019H as he want to keep learning how things are done.

I only came to satellite after 2000. For me all started by a code posted from csa.irde.to long time gone. But you can still find

https://web.archive.org/web/20040903151642/http://csa.irde.to/

There the posted a CSA source-code easily to understand. Author unknown. I am posting here simple code base on that

csasample.zip (1.40 MB)

https://workupload.com/file/ZJFcZZAN3M8

Pass:www.sat-universe.com

On the zip you will find a Codeblock project so that you can inspect code. But the easy way is to do

Encryption

make
csa_core.exe

Decryption do

cflags=-Ddencrypt make
csa_core.exe

There I am also providing you 5 E-Books o CSA. My bets is da_diett.pdf

 

[samur]

https://github.com/glenvt18/libdvbcsa

;

 

[cayoenrique]

@samur
YESS
I discussed libdvbcsa on my past and deleted Encryption Learning on our 3rd lab. Only we git clone from :

https://code.videolan.org/videolan/libdvbcsa.git

libdvbcsa is one of the most used libraries the other of is FFdecsa

https://github.com/gfto/tsdecrypt/tree/master/FFdecsa

The other code we have discussed for brute-force is aycwabtu that used libdvbcsa

https://github.com/aycwabtu/aycwabtu

samur thanks for the start. If you want to skip learning from beginning and just want to decode one of those libraries is what we need. Now those libraries are not easy to understand because by the years they have been manipulated to force use of new Single instruction, multiple data (SIMD) instructions set on our new CPU. So if you are good with SIMD & bitslicing then you can jump right at those library codes.

https://en.wikipedia.org/wiki/Single_instruction,_multiple_data
https://usubalang.github.io/usuba/2020/01/14/bitslicing.html
https://timtaubert.de/blog/2018/08/bitslicing-with-karnaugh-maps/

In the other hand to understand HOW CSA encrypt wee need to look at the basic code without any parallel code manipulation. That is where our little csa-core.c come into place. But samur will be correct if he remind us that csa-core.c is not the way to go for code inside a GPGPU. In GPGPU we need SIMD & bitslicing . libdvcsa code in our CUDA or OpenCL code may be the way to go.

I hope I did not confused the newbies.
Ignore what I said. We start from the basic csa-core. We look at some of the nice picture on the e-book. So we understand Key Schedule. Block Cypher and Stream Cypher. and how it all is put together. Once we know CSA I guess we put that inside GPGPU code and see how slow it goes. It will be our base line.

On the future, we can go and try to implement SIMD & bitslicing in order to speed things up. At that point some of the guys with newer GPU will love to have at lest 64bit implementations. But I guess to make it fair will try to write code at 32 bit word size.

 

[cayoenrique]

Please do not try to learn and understand next stuff. I personally do not know all that. But I know where to find it if I need it. For the most
part Wikipedia is the place, see below for links.

Methods of randomizing data or make them at least difficult to understand

In general the method of encryption is the only that requires a Key shared between sender and receiver.

Symmetric encryption algorithms use only one secret key to both encrypt and decrypt the data.

Asymmetric encryption algorithms use two keys, not one. This consists of a public key and a private key.

Hashing is similar to encryption in that it scrambles the input data into a randomized or near-randomized output data. Hashing differs significantly from encryption, however, in that it is a one-way process.
Salting the hash is the process of adding extra, randomized characters to the password.

Definitions taken from:

https://cybernews.com/security/hashing-vs-encryption/

Scrambler is a device that manipulates a data stream before transmitting.

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

Obfuscation is the obscuring of the intended meaning of communication by
making the message difficult to understand

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

Encoding is a system of rules to convert information into another form.

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

Cryptography definition

cipher is the same as cypher both are accepted.

cipher = (or cypher) is an algorithm for performing encryption (coding) or decryption (decoding)
Block size = an algorithm operating on fixed-length groups of bits: CSA = 64 bits (but effective 48 bits) , des = 64 bits ( but effective 56 bits) , AES128 = 128 bits etc
Symmetric-key algorithms = It is when the keys for decryption and encryption are exactly the same
Block cipher = is a symmetric key cipher which operates on a groups of bits of fixed length, called blocks
Stream cipher = A stream cipher is a symmetric key cipher where plain text digits are combined with a pseudo-random cipher digit stream (keystream).
S-Box = symmetric key algorithms which performs substitution.
Key size = the number of bits in a key used by a cipher. it define the actual degree of security. Bigger ,more secure.
Key expansion = Routine used to generate a series of Round Keys from the Cipher Key. 1 key result in multiple keys.
Diffusion = if we change one bit of the cipher-text, then approximately one half of the plain-text bits should change
Confusion = means that each binary digit (bit) of the cipher-text should depend on several parts of the key. This property makes it difficult to find the key from the cipher-text and if a single bit in a key is changed, the calculation of the values of most or all of the bits in the cipher-text will be affected.
padding = is any of a number of distinct practices which all include adding data to the beginning, middle, or end of a message prior to encryption.

A block cipher by itself allows encryption only of a single data block of the cipher's block length. For a variable-length message, the data must first be partitioned into separate cipher blocks. In the simplest case, known as electronic codebook (ECB) mode, a message is first split into separate blocks of the cipher's block size (possibly extending the last block with padding bits), and then each block is encrypted and decrypted independently. This problems led to Mode of operation and padding.

Modes of Operation
Electronic codebook (ECB)
Cipher block chaining (CBC)
Propagating CBC (PCBC)
Cipher feedback (CFB)
Output feedback (OFB)
Counter (CTR)

Block Cipher vs Stream Cipher
Block Cipher = Encrypt information in chunks. A block cipher breaks down plain-text messages into fixed-size blocks before converting them into cipher-text using a key.
Stream Cipher = Encrypt information bit-by-bit. A stream cipher, on the other hand, breaks a plaintext message down into single bits, which then are converted individually into ciphertext using key bits.

Info comes from the following:

https://en.wikipedia.org/wiki/XOR_cipher
https://en.wikipedia.org/wiki/Block_cipher
https://en.wikipedia.org/wiki/Stream_cipher
https://en.wikipedia.org/wiki/Pseudorandom
https://en.wikipedia.org/wiki/Symmetric-key_algorithm
https://en.wikipedia.org/wiki/Rijndael_key_schedule
https://en.wikipedia.org/wiki/Substitution_box
https://en.wikipedia.org/wiki/Padding_(cryptography)
https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation
https://en.wikipedia.org/wiki/Feistel_network
https://en.wikipedia.org/wiki/Substitution-permutation_network
https://en.wikipedia.org/wiki/Product_cipher
https://en.wikipedia.org/wiki/Square_(cipher)
https://www.thesslstore.com/blog/block-cipher-vs-stream-cipher/
http://www.faqs.org/faqs/cryptography-faq/part1/

MPEG Transport Stream (MPEG TS) encapsulates all data streams in cells of 188 bytes.
These cells consist of a 4 byte header and 184 bytes of payload.

So just remember CSA intent to encrypt/decrypt in general a payload of 184 bytes. But but CSA has a word size ( Block size ) of 8 bytes. This means CSA require 23 consecutive recurrent encryption to perform the full 184 bytes.

 

[cayoenrique]

I know too much Theory. BLAAAaaahhhh!

If you are a newbie. Lets go back to reality. Look at this 1rst image.

This a block diagram of what we need to mimic what Cudabiss does.

Cudabiss requirement is that we get 3 encrypted TS that have PUSI. We could do it with 2, as the third one is there to reduce false positive.

Lets describe what you see in the picture.
1) First can not forget that we start with encrypted data. The encrypted TS is at the TOP of the Image. At the bottom is the decrypted data. Where DB0 should look something like; 00 00 01 XX XX XX XX XX. We know this because we intentionally chose 3 PUSI TS.

2) Now lets describe the symbols:


The header

In a TS at least the 1rst 4 bytes are called the header. It always start with 47 XX XX XX. For the analysis we ignore this 4 bytes. So we do not even gave them numbers like 0-3. Nope, we just ignore they exist.


The encrypted data stream

B means BLOCK, for CSA BLOCK size = 8 Bytes. 8 bytes is 64 bits.
B0 means the 1rst of the block, or the 1rst 8 bytes of the stream.

S means Encrypted, the author used S for Scramble.
SB0 then means 1rst block of the encrypted data stream. Bytes 0-8
SB1 then means the second block of the encrypted data stream. Bytes 9-15.

N means the last Block, We said that TS payload size is 184 max. Then 184 / (8bytes per block) = 23 max block. But as we start from 0 then N = 22 ( not 23 ).

SBN then means that last block or SB22. I hope you see how it goes.


Intermediate ( Internal ) encrypted data stream

I means Intermediate
IB0 is the 1rst Intermediate Block.


Data stream in the Clear ( Unencrypted )
D the author choose D as for Data in the clear.
DB0 means the 1rst unencrypted data block.


IV the Initial Vector
IV is just an 8 Byte block. In CSA is just 00 00 00 00 00 00 00 00. This means we can ALWAYS ignore they exist. It does not do anything, period.

XOR the xor bit operand
Just remember, this means that;
if bits of the inputs are equal, the result bit is 0
if bits of the inputs are different, the result bit is 1


KEY the key to be used
The KEY has a length of 8 byte. But we going to do 23 operation. This mean we need 22 more keys. The other 22 keys are going to be derived from the 1rst key. This process that generate more keys from the 1rst one is called Key Schedule.

Block Cypher
As the theory said is a processes that uses a Key to hide the original values. In CSA is 8 byte long. This block cypher uses loop and a key to change or hide the original value. It also uses what is called a SBLOCK table. Blocks Cyphers works for the most part in parallel.

Stream Cypher
It is also another processes that uses a Key to hide the original values. But instead of 8 parallel byte, here it try to work in bits. CSA Stream cypher is very complicated it has many register of different sizes. It even has its own sboxes to obfuscate the values.

I know you are going to tell me we still in theory. HE HE HE

 

[C0der]

Which GPUs (finally) have 64bit-registers?

 

[cayoenrique]

I know. But my AMD may not do 64 bit. Meaning I can not test at home before posting. That is what I can only warranty that I can test 32bit. Will see when we cross that bridge.

To all. I forgot to conclude. At the end we need to compute 1 Block cypher and 1 stream cypher. Key schedule in for the most part unimportant.

 

[cayoenrique]

@C0der

Ups! I did not understood you are asking me. Well I assume that new Nvidia GPU are 64bit register. Are they? I do not know. I will try to check.

 

[cayoenrique]

Quick search fail to find 64bit GPU.

Now CPU went 64 bit in order to handle more that 4GB of memory.
Then the question is what modern GPU do to handle more that 4 GB of ram efficiently. I know they could do pageing like old 16bit CPU did.
I guess will will work in 32bit unless some one probe we are wrong.

 

[K2TSET]

Hi cayoenrique, nice work you are doing here to get people involved in the CSA / GPU BF

I really hope that there are some new findings which can bypass some of the Algo in the BF search.

I did look into GPU quite some years ago and did find that they always did work as 32 bit even if the code was written as 64bit in VisualStudio with cuda support.
I read somewhere that if Intel compiler was used then cuda code would be as 64bit, but there were still an issue with the registers in the SM was only 32bit and if you defined as 64 it just uses 2 registers.
If that is different on AMD or changed with never NVIDIA GPU's I don't know.

The biggest problem back then was to do all the SBOX lookup in the BC since you have to do that for every round and there was to less registers in the SM / Block / Grid / Thread to have all 256 bytes on all cores.
Whatever I tried with the lookup and memory types it could not fit inside the core, and did run slow fetching data from memory somewhere else.
The problem is that all cores have to do the SBOX lookup constant (every round) and this was a big bottleneck at that time. this might be different with newer GPU cards.

Doing SC are way faster than BC both on CPU / GPU and also in FPGA due to the small size of the 7 Sboxes are converted to logic, but if you try that with 256Bytes in BC it logic becomes very large and = slow.

I did a lot of test with FPGA solutions since there were so many parts of the Algo which could be done on every clock cycle and quite some part of the Algo which could be reduced due to the nature of how a FPGA works.


A little correction to your writing:
"KEY the key to be used
The KEY has a length of 8 byte. But we going to do 23 operation. This mean we need 22 more keys. The other 22 keys are going to be derived from the 1rst key. This process that generate more keys from the 1rst one is called Key Schedule."

We are not going for 23 round for BF, only 1 BC (56 rounds) and 1 SC (32 init rounds + 24 run rounds)
The Key Schedule are only used in the BC and the 8 bytes are permuted (new positions of bits) 7 times which gives 56Bytes and 1 bytes are used on every rounds of the BC which have 56 rounds (where we need the SBOX lookup)

 

[C0der]

PTX ISA 8.2 (which should include the RTX4090) states "each multiprocessor has ... one set of local 32-bit registers per processor"
So, still 32 bit, i guess.

 

[cayoenrique]

@all I did mention 64bit because was an old assumption. That once GPU used more than 4 GB of RAM, it was logic to move into 64bit just like CPU did. Now, I read that no mater what 3D rendering requires only 32 bit Integer size. Then it seems in the other hand unnecessary to have bigger Integer size. So, one more time, It was a wrong assumption I did.

@K2TSET
It is nice to see you. I always thank you for the help you had provided me in the past even if I got no positive solution. I did try and fail to find a possible schema to the new unknown Tandberg video decode process. The rolling keys but no video.

And I do not know if you remember, but I did commented to you in the past on: Doing SC are way faster than BC both on CPU / GPU . I get the opposite some how. This is why I never finish my cudabiss alternative.

Regards the rest I agree 100%. Reading to tables has the major effect slowing the process. Also big need of resources, finally end up eating out ( canceling) a big amount of cores.

To the newbie why reading to tables is so bad.

Imaging a Football Arena. It is build so that 100,000 people can exit the arena in minute, let say 15 minutes. This is because under normal circumstances only a very few exit thru the doors at one time. No doubt that most of the people move slow but they move.

Then a Kid explode a rubber balloon and people get scare and start running. All trying to exit at once. A stampede. As a result instead of going faster they all collide stopping the movement to almost no movement. And now it take hours for the rest to be able to leave. As a result running instead of going faster end ups slowing it down.

Same happen in GPU waves. It is expected to be parallel process, GPU scheduler expect that all cores read same memory position. At most waves can read consecutive memories aligned with their position in the wave. This is core 0 read memory 0, core1 read memory 1, etc. But reading tables to change values is not predictable not sequential, Every core may have to read at any position of the table. This is Random access. The GPU schedule stop the Parallel Wave. Then allows only 1 core to in the wave to read at a time. Yes 1 read the other have to wait doing nothing. Result is that a single read to memory stop all parallel process and the advantage of a GPU. Now imagine a 56 round, in each round each core you read twice one SBOX one Permute.

Finally, there is one SU user that hope/expect we do better but in magnitude. Like cutting in half the time. I already said 20 years of waiting prove it is not easy.
Now I am here for @Me2019H he was the one to call me from retirement to continue some teaching. The Idea is to show how GPU computation can be done. At most, some of you guys will having a tool for AMD GPU.


I was expecting to have Windows issues with Nvidia cards. Instead we had Issues with Nvidia but in Linux. So as an update, for the last days I been trying to resolve that little issue so that @Me2019H can continue with us. I have not forgotten this thread or T2MI app. I will be back soon with next lesson for the newbies.

 

[cayoenrique]

OK back to CSA review.

In CSA Decrypt (BFA) Brute Force Attack we start with Encrypted data, to be exact 2 Blocks SB0 + SB1. These are 16 bytes total. SB0 is use only as initialization for the Stream Cypher and the Block Cypher. Now to get the Result of DB0 we need 1 Block Cypher and 1 Stream Cypher. The data coming out from Stream Cypher is CB1. For the drawing the author did not created a result of Block Cypher1 but lets called BC1. The resulting equation will be.

In math some time we represent XOR as “^”


(Clear DATA 1) = (Encrypted DATA 1) XOR (result Stream Cypher 1) XOR ( result Block Cypher 1)

DB0 = SB1 XOR CB1 XOR BC1

or

DB0 = SB1 ^ CB1 ^ BC1

I know you hate MATH. There is no other way to attack this we always need math.

Now what are this Stream Cypher and Block Cypher. This are complex mathematical functions. They use loops, feedback, rotation, shift, permutations and table substitution to obfuscate a value by transforming it. The loops and tables are the most important. Big amount of loops ensure that the process require lots of time to be resolve. Table substitution in the other are there as NONE Linear elements. This none linear elements prevent the use of simplification of math equations. So no matter how good I am in math I can not simplify that equation. All this warranty that lots of time is require per key solution. This means if I try BFA I will take more than a man’s life time resolve all key values.

A simplify description of the difference of Stream vs Block is:
In general both are as hard to work in GPU.

Stream Cypher

Work in bits
Equations are not easy to do in parallel but Tables are easier because they are smaller less to read

block cypher

Work in blocks of bytes
Equations more simper easy to do in parallel but Tables are larger harder to read


Have a carefully look at the drawings. In stream you see the work bits a lot
You can also see how complex the stream cypher is compared to block cypher.[/b]

 

[K2TSET]

The Block Cypher posted above is for Encoding

Here you have the Block Cypher for Decoding which we want to use for BF

Here as 4 rounds of BC (total 56) it's easy to see how the flow goes over several rounds, this makes it possible to see where it might be worth to make calculations for 2 rounds in one go, also it's very clear why we need the Sbox lookup on every rounds

2 x Stream Cipher witch are the same for both encoding and decoding, you will see that the E and F signals are bypased from 1 round to the next one so here are some benefit in doing calculation at the same time.

All the blue labels are only done on the 32 first "Init rounds"
All the red labels are only done on the "run rounds" (where we get 2 bit out per rounds) so we only need 12 rounds of the runs to get 24bit to look for the 00 00 01

I did made a flow diagram some time ago for all rounds with test values needed for a BF setup

The values came form a clean TS I did encrypt with the key "11 22 33 44 55 66 FF"

The top values "29 E8 6B ..... " are the encrypted data from 1 PUSI
The lower value "24 15 77 ...." are the encrypted data from 2 PUSI

When we get the 00 00 01 output based on the first PUSI there is a potential hit and we do a test with the 2 PUSI to see it's 00 00 01 as well

Hope it helps to understand the flow of the BF

 

[C0der]

There is a paper out there titled "Weaknesses in the Initialisation Process of the Common Scrambling Algorithm Stream Cipher".
Anybody got a pdf of that?

 

[cayoenrique]

@C0der did not lost his pictures. I remember seeing those nice pictures in old threads. THANKS.

As a pay back here is what you are looking

You can found as part of lecture-notes-in-computer-science-sequences-and-their-applications volume 8865 page 220

weekness.zip (7.90 MB)

https://workupload.com/file/hmPQZ8zeaks

Pass:www.sat-universe.com

 

[C0der]

Thanks.
(I think you mean K2TSET with the pictures tho.)

 

[cayoenrique]

HE HE HE...
My respect to @K2TSET. Please forgive me.
Ohh! Boy you C0der are correct. I am getting old and my mind is failing. Never the less you where in the discussion 10 or so years ago with @kebien, @K2TSET and a few others.

 

[cayoenrique]

Ok lets see if we can do this quick.

On post #1 I gave you a C program. That is good to encrypt or decrypt a full ts ( 188 bytes).

But now we focus in Brute force attack BFA. 1 rst we need to decrypt ONLY. So all routines dedicated to encryption was deleted. Now look again to image

Most is gray out, than means we do not need to do that. We only need to decrypt 1 block. So here a new C program that those that. 1 block decrypt.

csa_decrypt_1block.zip (9.09 KB)

https://workupload.com/file/83DLWnyqV3U

as always pass:www.sat-universe.com

At the top you will see

uint8_t key_perm[0x40] 
int sbox1[0x20]
int sbox2[0x20] 
int sbox3[0x20]
int sbox4[0x20]
int sbox5[0x20] 
int sbox6[0x20]
int sbox7[0x20] 
uint8_t block_sbox[0x100]
uint8_t block_perm[0x100]

This are all CONSTANT they do not change. In opencl we will assigned them to __constant memory. because constant is faster than global memory. And too big to be in __private.

Now If you inspect carefully I already started to make modifications for OpenCL. In the theory I explained we need to use as little registers as possible. The original author use arrays from 1 to N. Ignoring that there is a 0. So I replace those arrays so that they used 0. This means for each array variable I am saving 1 private memory location!! This are

A[1]-A[10]		A[0]-A[9]
B[1]-B[10]		B[0]-B[9]
kk[1]-kk[56]	kk[0]-kk[55]
R[1]-R[9]		R[0]-R[8]

I am not going to talk about that key_schedule. It is to complex and do to many unnecessary stuff. Soon you will see what we do with it.

stream_cypher we will have trouble as some of the registers need to be static.

    static int A[10];
    static int B[10];
    static int X;
    static int Y;
    static int Z;
    static int D;
    static int E;
    static int F;
    static int p;
    static int q;
    static int r;

This tell the compiler to save the values for nest used. This is not permitted in Opencl lower than 1.2. Not sure what version it may be allow. So we will mod this one soon.

And all decrypt magics now happen in decrypt1b, as this ONLY decrypt one block.

The output is like:

enrique@live:$ cd csa_decrypt_1block
enrique@live:$ make
Detected OS = Linux
CFLAGS = -Wall -g -fopenmp -std=gnu11 -DCL_TARGET_OPENCL_VERSION=110 -D__OPENCL_VERSION__=110
INC_DIRS = 
LIB_DIRS = 
LIBS = -lgomp -lOpenCL
CC = gcc
STRIP = strip
RM = rm -f
RRM = rm -f r
srcfiles = ./csa.c ./csa_decrypt_1block.c
objects =  ./csa.o  ./csa_decrypt_1block.o
BIN = csa_decrypt_1block
gcc -Wall -g -fopenmp -std=gnu11 -DCL_TARGET_OPENCL_VERSION=110 -D__OPENCL_VERSION__=110 -c ./csa.c ./csa_decrypt_1block.c
CC	csa.c
g++   ./csa.o  ./csa_decrypt_1block.o   -lgomp -lOpenCL  -o csa_decrypt_1block
strip csa_decrypt_1block
enrique@live:$ ./csa_decrypt_1block

encrypted
0000 - 47 41 00 1A 3C EB DC 17 3C 2B D6 4F 65 16 88 F2 
0010 - 58 D5 97 05 


Key				 38 5F 62 F9 4F CA BC D5          8_b.O... 

key schedule, kk[0]..kk[55] = 
 70 F8 7D A8 CC 8D 9D BF A6 6E EF E8 3D 93 AB 6D          p........n..=..m 
 D5 28 25 31 CB 3D 0D 9D 13 EE AC EF 0F ED BE F2          .(%1.=.......... 
 2B 4F A2 7F AF 99 BE 22 13 AB 33 22 E9 EC 42 FE          +O....."..3"..B. 
 3E 59 64 FF 49 CC BA D3


SB[ 0]  = 3C EB DC 17 3C 2B D6 4F		65 16 88 F2 58 D5 97 05

IB[ 0]  = 3C EB DC 17 3C 2B D6 4F 
stream  = 								63 C9 50 DD C4 0A E8 F3 
IB[ 1]  = 								06 DF D8 2F 9C DF 7F F6 
block   = 								06 DF D9 CF 9C DF FF 36 
DB[0] = 								00 00 01 E0 00 00 80 C0 
enrique@live:$

 

[dvlajkovic]

You've left the wrong compiler in *.cbp
Need to replace all the lines that read
<Option compiler="gcc" />
with
<Option compiler="opencl_msys2" />
Then it builds OK.
When *exe has been ran it delivers the same as in linux