brmlab project:gsm:deka

Attack implementation

Anonymous (anonymous@undisclosed.example.com) — 2015-08-27T15:25:35+00:00

1440688857	current
Line 1:	Line 1:
	+	~~NOTOC~~
	+	====== Attack implementation ======
	+
	+	This document describes an efficient A5/1 implementation on SIMD hardware. Then, a fast method for hard-drive lookups on Linux is described.
	+
	+	===== Cipher overview =====
	+
	+	Read basic operation in a [[https://en.wikipedia.org/wiki/A5/1#Description\|Wikipedia article]] if you have never seen it before.
	+
	+	You can find some example implementations around the internets. They usually work like this:
	+
	+	* Extract the clocking bits from the registers (bitshift + AND)
	+	* Compare majority clocking bits (some logical operations and a conditional branch)
	+	* Compute next bits (several conditional branches and logical operations)
	+	* Update registers with these bits (bitshift)
	+
	+	Running the aforementioned naive implementation on ATI HD7970 card gives us about 90 Mkey/s. The conditional branches don't really suit the GPU architecture and the registers are only 20 bits long, whereas the card can process 64bit long data types.
	+
	+	===== Bitslicing =====
	+
	+	[[https://web.archive.org/web/20131021214351/http://plaintext.crypto.lo.gy/article/378/untwisted-bit-sliced-tea-time\|crypto.lo.gy article on bitslicing]]
	+
	+	[[https://en.wikipedia.org/wiki/Bit_slicing#Modern_use\|Wikipedia article]]
	+
	+	We will run multiple A5/1 instances in parallel. We will achieve this by loading 64 A5/1 instances somewhat "rotated" into 64 registers that are 64 bits long.
	+
	+	<code>
	+	64*64bit variables (vertical) - r[64] array
	+
	+	↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
	+	+-+-+-+-+-+-+-+-+
	+	\| \| \| \| \| \| \| \| \| ← A5/1 instance #1 (registers concatenated)
	+	\| \| \| \| \| \| \| \| \| ← A5/1 instance #2
	+	\| \| \| \| \| \| \| \| \| ← A5/1 instance #3
	+	\| \| \| \| \| \| \| \| \| ...
	+	\| \| \| \| \| \| \| \| \|
	+	\| \| \| \| \| \| \| \| \|
	+	\| \| \| \| \| \| \| \| \|
	+	\| \| \| \| \| \| \| \| \|
	+	+-+-+-+-+-+-+-+-+
	+	</code>
	+
	+	Now for example register shifting is done by circular assignment
	+
	+	<code>
	+	for(i=18; i>0; i--) {
	+	r[i] = r[i-1];
	+	}
	+	</code>
	+	This rotates registers of all A5/1 instances at once.
	+
	+	Another popular operation in A5/1 is bitwise XOR. Again, XORing r[i] with r[j] XORs the bits i and j in all A5/1 instances - with a single instruction!
	+
	+	The original Kraken written by SRLabs in 2009 used hand-vectorized assembly-resembling C. We believed that 2015 compilers will unroll the loops and then convert all these commands into vector instructions for us. So for example XORing would be done by the vector unit 256 bits at once and circular assignments would be done by efficient vector rotation instructions. And the whole thing would use only 16 vector registers instead of 64 general purpose registers. However, it turned out the compiler sucks at this and it generates code that is even slower than the naive implementation. So we had to do the vectorization by hand. To produce a better maintainable code, we generate the C code with a shell script.
	+
	+	This is implemented in genkernel* shell scripts.
	+
	+	<note tip>We found out that using 128-bit vectors (432 bit) is about 8 times faster (and hence 4 times faster in total as shorter vectors process less data) than using 256-bit vectors (464 bit) on our AMD HD 7970. We hypothesize long vectors won't fit into L1 cache. It may not be the case on other hardware, so we ship "genkernel32" and "genkernel64". Pick the one that is faster on your hardware.</note>
	+
	+	With this implementation, we get 1.2 Gkey/s on AMD HD 7970.
	+
	+	==== Irregular clocking ====
	+
	+	However, we need to clock two register and the third not - and this is different in each clocking for each cipher instance. So let's create three vectors - called clock1, clock2 and clock3 - each containing "1" on the given position when the given register of the given instance shall be clocked. Now we can clock the register with
	+
	+	<code>
	+	r[i] = (r[i] & ~clock1) \| (r[i-1] & clock1);
	+	</code>
	+
	+	If the register is clocked, clock1 will have "1" and the right part of the expression will apply. Otherwise, the register will be overwritten by itself.
	+
	+	===== Table lookup =====
	+
	+	If the tables are sorted, you can find the endpoint in log(n) time, or about 35 seeks in table of size 2^35 (32 GiB). Disk seeks are the bottleneck of the attack. Let's do it better:
	+
	+	At first, we notice that the endpoint values are evenly distributed from 0x0000 to 0xFFFF. Hence we can limit the first part of binary search to a smaller area than the whole disk.
	+
	+	Then, we notice that we have several gigabytes of RAM that is much faster than the drive, and that drive works with "blocks" (usually 4 KiB on current hardware). We will compute the index, which has for each 4KiB block its starting value. Then we will do the binary search in the index in RAM and then load one block that contains the solution.
	+
	+	The 32GiB table consists of 8 Mi blocks and you need 8 bytes for a block, so the index will take about 64 MiB RAM - no problem with current computers.
	+
	+	This is implemented in TableConvert from original Kraken.
	+
	+	===== Table encoding =====
	+
	+	Naive table would contain tuples "(starting value, endpoint)". We will notice that the endpoint has 12 bits zero by definition, but it still takes 2*64-12 = 116 bits.
	+
	+	Let's encode the starting point better. We don't need the whole 64 bits, as we have only about 2^34 chains in one table (less in the tables released, probably due to merges). Let's take a 34bit value and a hashing function that hashes to 64 bits (I guess that it's not a good idea to just pad it with zeros as the A5/1 machine might go nuts). This is the magic with kr02_whitening() and kr02_mergebits() you can see in delta.c. The 0x93cbc4077efddc15ULL constant is probably taken from some Linear Congruential Generator, but I haven't found any more info on this.
	+
	+	Now we have 34+64-12 = 86 bits.
	+
	+	The tables are sorted by endpoints and when there are ~2^32 evenly distributed points in 2^52 space (2^64 space minus 12 bits that are always zero), the average gap will be 2^20. So let's encode the endpoint with only 20 bits (+ some margin/padding, as we need variable length encoding). One chain then takes on average only 34+20 = 54 bits.
	+
	+	This is called delta encoding and you can see the parser in delta.c. The format is not documented and we did not want to mess with it, so we edited the three functions (StartEndpointSearch, CompleteEndpointSearch and load_idx) from DeltaLookup from the original Kraken to be compilable with GCC and used them as-is.
	+
	+	Original Kraken is a mix of non-free code and code with unstated license (presumably written by someone else) - DeltaLookup is the unstated case. We tried to contact the author to clarify the license situation and we received no reply. We believe using a small interface to binary undocumented format can be treated as fair use.
	+
	+	===== Reading blocks =====
	+
	+	So now we know which block we want. Straightforward method would be to open the device, fseek() to a desired position, and fread() the block.
	+
	+	We ran this on a SSD and we got about 5000 IOPS - far less than what was advertised on the SSD product sheet. The problem is the latency - your request goes through the kernel, controller, SATA and SSD controller. The latency of 200 μs seems good, but we would like to get it better.
	+
	+	Current hardware supports [[https://en.wikipedia.org/wiki/Native_Command_Queuing\|NCQ]]. It can queue several (~32) commands. This is good both for rotation drives, as the commands can be executed in optimal order, and for SSDs, as this eliminates the latency. Linux kernel supports NCQ.
	+
	+	We have 4 SSD drives and the queue for each is 32 commands long. Having the application run in 128 threads sounds like a thread-synchronization nightmare to me. We will rather use the madvise() function and leave the parallelism to the kernel. We flag the blocks we need as MADV_WILLNEED and the kernel will cache the pages in question to memory. We can then just read them. Oh, and use MADV_RANDOM to disable readahead and MADV_DONTNEED once we got it to free the memory.
	+
	+	This is also implemented in delta.c.
	+
	+	Original Kraken uses the following approach:
	+
	+	* mmap the 4096 long block
	+	* madvise it
	+	* wait until it is ready (mmap and madvise other blocks meanwhile)
	+	* read it
	+	* munmap it
	+
	+	We have run this on Linux 3.2 and the mmap and munmap system calls were very inefficient (no idea whether it was misconfigured or if it is just a feature). So we mmapped the whole device. We achieved a 14 % performance gain by it. mmap()ing 1.7 TB is possible on 64-bit system and I don't think someone would run such application on something 32-bit.

A5/1 TMTO attack description

Anonymous (anonymous@undisclosed.example.com) — 2015-12-17T21:17:02+00:00

1440732686	current
Line 1:	Line 1:
	+	~~NOTOC~~
	+	==== A5/1 TMTO attack description ====

	+	<note>TL;DR You can go through the A5/1 keyspace and save some "distinguished points". When you want to recover the key, you reconstruct the keyspace from the nearest distinguished point.</note>
	+
	+	<note tip>This document contains theoretical description of the attack. There is [[attack-implementation\|another one]] that describes the actual implementation.</note>
	+
	+	===== Cipher basics =====
	+
	+	Symmetric cipher takes plaintext and key and creates ciphertext. The other party of the communication takes the ciphertext and the very same key and uses the cipher to decrypt it to plaintext.
	+
	+	Some symmetric ciphers are block ciphers. They operate on blocks of fixed size. They take block of plaintext (usually 64-128 bits) and create block of ciphertext (of the same size). Examples of block ciphers are AES, Blowfish, DES.
	+
	+	{{https://www.abclinuxu.cz/images/clanky/hrach/gsm02-block.png?300}}
	+	<code>
	+	plaintext
	+	\|
	+	v
	+	key ----> cipher
	+	\|
	+	v
	+	ciphertext
	+	</code>
	+
	+	Other case of symmetric ciphers are stream ciphers. The key is used to initialize a pseudorandom number generator (PRNG) and the PRNG generates a sequence called keystream. The keystream is then used as one-time-pad, it is XORed with plaintext. The other party of communication initializes its PRNG with the same key, generates the very same keystream and XORs it with ciphertext. The plaintext appears. Examples of stream ciphers are RC-4 and A5/1
	+
	+	{{https://www.abclinuxu.cz/images/clanky/hrach/gsm02-stream.png?300}}
	+	<code>
	+	plaintext
	+	XOR
	+	key ---> PRNG ---> keystream
	+	\|
	+	v
	+	ciphertext
	+	</code>
	+
	+	(note: block ciphers can be easily modified to stream ciphers)
	+
	+	Stream ciphers are popular for telecommunications. Flipping one bit in block cipher ciphertext destroys the whole block, whereas flipping one bit in stream cipher destroys only this one bit. Hence communication is possible even with weak signal when occasional problems in reception occur.
	+
	+	It is very important not to use one key multiple times, as the one-time-pad property would be destroyed. In GSM, the session key (called Kc, 64-bit) is concatenated with frame number (22-bit) and the resulting 86 bits are used for A5/1 PRNG initialization.
	+
	+	The 22-bit frame number rolls over every 3.75 hours. This is longer than the interval of standard rekeying. Additionally, the attacker will have to match the exact frame which is difficult in network with lots of latency. The attack on this is not practical.
	+
	+	===== A5/1 basics =====
	+
	+	Have a look at the A5/1 cipher (source: [[https://en.wikipedia.org/wiki/A5/1#Description\|Wikipedia]])
	+
	+	{{https://upload.wikimedia.org/wikipedia/commons/thumb/5/5e/A5-1_GSM_cipher.svg/320px-A5-1_GSM_cipher.svg.png}}
	+
	+	It consists of 3 shift registers of 64 bits total and several XOR gates. When you are clocking the registers, they spit out pseudo-random bits. These are used as keystream.
	+
	+	The cipher has a "secret state" (or "internal state") defined by values in the shift registers. Once you recover that secret state, you can load it to your cipher and generate the keystream from that point on (and decrypt the rest of the current burst - A5/1 is reinitialized on each burst in GSM). Moreover, you can [[http://web.archive.org/web/20100710081708/http://reflextor.com/trac/a51/wiki/BackclockA51\|backclock]] the cipher by running the shift registers widdershins and recover previous keystream and even the key itself. The solutions for counter-clockwise running are sometimes ambiguous (e.g., sometimes you cannot determine the input to a XOR gate given the result), however, you usually get a few dozens of key candidates, which you can just try. Backclocking is implemented in find_kc utility from kraken-utils.
	+
	+	Recovering cipher secret state is what we want to do.
	+
	+	===== Naive approach =====
	+
	+	Notice that the internal state is only 64 bits. It is possible to run naive bruteforce with modern hardware. It will take about 100 years with our A5/1 implementation on an AMD HD 7970 GPU and is infinitely parallelizable. It is impractical, as on standard GSM cell you have several communications each minute.
	+
	+	===== Precomputed table =====
	+
	+	You can compute the table mapping internal state to keystream.
	+
	+	<code>
	+	Internal state Keystream
	+	0x0000000000000000 0xabcdef12345678
	+	0x0000000000000001 0x54632221afed03
	+	0x0000000000000002 0x456dcd562b980e
	+	...
	+	0xffffffffffffffff 0x002accd4dc51df
	+	</code>
	+
	+	Once you observe a certain keystream in the air, you can just look up in the table the corresponding internal state. The table can be sorted by the keystream resulting in very efficient (logarithmic) lookups.
	+
	+	However, such table is big. Naively it is 2^64 states * 8 bytes per state = 128 Exabytes.
	+
	+	{{ :project:gsm:deka:128eib.png?direct&600 \|}}
	+
	+	The effective keyspace is only about 61 bits (because of the solution ambiguity, several states in the cipher [[http://web.archive.org/web/20100710081708/http://reflextor.com/trac/a51/wiki/BackclockA51\|collapse]] to one resulting state), though it is not practical to store Exabytes if you are not a NSA.
	+
	+	===== Keystream extraction =====
	+
	+	Oh by the way how do you get that keystream when you know only ciphertext? Well ciphertext = keystream XOR plaintext and hence keystream = ciphertext XOR plaintext. You can try to guess the plaintext and it seems to be rather easy. In GSM it is not possible for a BTS to stop transmission as the phones will lose synchronization. Then even when it has nothing to say, it transmits frames full of padding. So let's XOR the padding (plaintext) with the captured ciphertext to obtain keystream.
	+
	+	One countermeasure to this attack for the operators is to randomize the padding (and other deterministic data, like list of neighboring cells). This faces some technical difficulties in the protocol which are out of scope of this description. Additionally, plaintext recovery heuristics can really improve this attack. For example napalmex from brmlab's GSM stack contains an efficient implementation of this resulting in almost 100% chance of key recovery on insecure networks (like O2 or Vodafone) and 40-50% success rate even on secured networks like T-Mobile.
	+
	+	See [[project:gsm:guesser]]
	+	===== Table optimization =====
	+
	+	Let's try to compress the naive lookup table by creating chains. We take a starting secret state, use it as an A5/1 input, and we will not save the result, but use it as another A5/1 input. And then again until we get into a distinguished point (DP). DP can be defined for example by having 12 least significant bits zero. This gives the average chain length of 2^12 = 4096 and the compression ratio 1:4096 (it is worse, read on).
	+
	+	Once you get a keystream to crack, you use it as an input to this chain generator and run it until you reach a distinguished point. Then you look up in your table corresponding starting point and generate the chain again. The chainlink immediately preceding your keystream is the secret value you are interested in.
	+
	+	We have compressed the table chainlength times at a price of worsening the lookup time in a sorted table from log(N) to log(N)+chainlength. This is called time-memory tradeoff.
	+
	+	===== Merges =====
	+
	+	Unfortunately, given the cipher ambiguity again, sometimes several chains merge into one. You have then several data multiple times or you don't have some "branches" of the keyspace at all. This is an especially important problem if you lengthen the chain to achieve higher compression ratio.
	+
	+	Merges can be reduced by splitting long chains using colors (this is why these tables are called rainbow tables). We have to change our chain generator by introducing a reduction function. So far it was
	+
	+	* check for DP
	+	* if there is DP, return
	+	* generate keystream
	+
	+	Now it is
	+
	+	* apply reduction function
	+	* check for DP
	+	* if there is DP, increment color
	+	* if color > max_color, return
	+	* generate keystream
	+
	+	The reduction function in the easiest form is XORing by a predefined constant. Different colors are assigned different constants. Hence, parts of chains are XORed by different constants. If a merge appears in distinct colors, it is broken by different constants in the next round.
	+
	+	===== Table coverage for GSM =====
	+
	+	Rainbow tables can't cover 100% of the keyspace as you will never go through all states when generating (random) chains. But we don't care -- in GSM, every frame consists of 4 bursts, 114 bits each. The sample we are trying to crack is 64bits long and hence you have 51 samples per burst or 204 samples per frame. To get a 50% chance to crack a given single frame, you need to cover less than 0.5% of the keyspace! And you usually get more than one frame from a GSM communication.
	+
	+	Thus, we have reduced the size of the naive table:
	+
	+	* Naive table: 128 EiB, 148 EB
	+	* After keyspace collapse by 3 bits: 18 EB
	+	* After introducing chains of length 4096: 4.5 PB
	+	* After introducing 8 colors: 563 TB
	+	* After reducing coverage to 0.5%: 2.8 TB
	+
	+	3TB drive costs $150 as of August 2014.
	+
	+	Please go read [[https://srlabs.de/blog/wp-content/uploads/2010/07/Attacking.Phone_.Privacy_Karsten.Nohl_1.pdf\|the original Karsten Nohl's paper]] and [[http://www.mail-archive.com/a51@lists.reflextor.com/msg00122/090929.Rainbow.Tables.XLS\|detailed analysis]] for a more accurate estimate.
	+
	+	Links:
	+
	+	* [[http://www.mail-archive.com/a51@lists.reflextor.com/\|A5/1 cracking project]] - mailing list archive
	+	* [[https://srlabs.de/decrypting_gsm/\|SRLabs]] - Decrypting GSM
	+	* <html>git://git.srlabs.de/kraken</html> Kraken source
	+	* [[https://opensource.srlabs.de/projects/a51-decrypt\|A5/1 decryption wiki]]
	+	* [[https://www.youtube.com/watch?v=ZrbatnnRxFc\|Wideband GSM sniffing]] - SRLabs 27c3 talk
	+	* [[https://www.youtube.com/watch?v=LgZAI3DdUA4\|A5/1 animation]]
	+	* [[https://www.abclinuxu.cz/clanky/na-gsm-s-osmocombb\|My article on GSM sniffing (in Czech)]]
	+	* [[https://www.abclinuxu.cz/clanky/utoky-na-gsm\|My article on GSM attacks (in Czech)]]
	+	* [[http://nat.brmlab.cz/talks/2013-12-19-utoky-na-gsm.mkv\|My talk on GSM attacks (in Czech)]]
	+	* [[http://nat.brmlab.cz/talks/2013-12-13-crackovani-sifer-s-opencl.mkv\|My talk on efficient A5/1 implementation using OpenCL (in Czech)]]

Installing deka

Anonymous (anonymous@undisclosed.example.com) — 2017-01-16T15:40:37+00:00

1456228264		current
Line 16:		Line 16:
	===== Installing tables =====		===== Installing tables =====

-	Install the tables. It should be done by configuring indexes/tables.conf and running indexes/Behemoth.py script, but I have never done it with this script. I did it manually and it is something like this	+	It is to be done this way

	<code>		<code>
Line 22:		Line 22:
	# table format source file destination:offset index destination</code>		# table format source file destination:offset index destination</code>

-	if stored in files or	+	if stored in files. However, to avoid filesystem overhead, a direct installation on a block device is advised. The install.py script should help you with this.
-		+
-	<code>./TableConvert di /mnt/tables/gsm/100.dlt /dev/sda:<offset> 100.idx</code>	+
-		+
-	if stored on raw disk device, which could result in lower overhead for each table file. To store multiple tables on the same drive, specify the offset (in 4KiB blocks) or use LVM LVs if you don't want to mess with it.	+
	===== Configuring tables for deka =====		===== Configuring tables for deka =====

Architecture overview

Anonymous (anonymous@undisclosed.example.com) — 2015-09-02T03:38:08+00:00

1441059411	current
Line 1:	Line 1:
	+	====== Architecture overview ======
	+
	+	paplon is the TCP server. It queues work.
	+
	+	oclvankus downloads work for chain computation. It uses slice.c OpenCL kernel. The kernel is generated by genkernel scripts.
	+
	+	delta_client downloads work for table lookup.
	+
	+	Most of it is Python. oclvankus OpenCL interface was very slow in Python, so several key functions were rewritten to C and wrapped with swig. This is called libvankus.
	+
	+	delta lookups are facilitated by functions in delta.c, again, linked with swig to delta_client.
	+
	+	The cracking process works like this:
	+	* Client submits "crack 010101…" on tcp/1578
	+	* The keystream is sent to oclvankus. Distinguished points are computed and burst is returned.
	+	* Distinguished points are sent to delta_client. Corresponding starting points are looked up in the tables. If nothing is found, zeros are returned.
	+	* Keystream and starting points are sent to oclvankus. The chains are regenerated from the starting points and compared to the keystream. If secret states (the chainlink immediately preceding a successful comparison) are found, they are sent to paplon and then to clients.
	+
	+	===== Network protocol =====
	+
	+	Client connects to server and sends "command param1 param2 .. paramN\r\n<binary data>" (command and parameters are separated by spaces). Parameters are command-dependent, usually one of them specifies the length of the binary part (if there is any).
	+
	+	The response is in similar format.
	+
	+	Client-exposed commands are "crack" and "stats". "crack" accepts keystream as a parameter, "stats" has no parameter and prints out some info about server load (namely how many bursts are in which stage of cracking).
	+
	+	Internal commands are the rq_* functions in source code. We provide python docstrings for them, keeping a copy in wiki would be prone to obsolence.
	+
	+	===== Keystream data format =====
	+
	+	Keystream is 114 bits in ASCII (string of ASCII '0's and '1's). Example: client sends:
	+	<code>
	+	crack 110000111101111011011100000111011000010010011010101010110010100010010101010101000110010101011010101000101001000000
	+	</code>
	+
	+	===== Burst data format =====
	+
	+	Bursts are sent 1) with computed endpoints (to delta_client), 2) with corresponding startpoints (from delta_client).
	+
	+	Burst is composed of number_of_tables * number_of_keystream_samples * number_of_colors = 40 * 51 * 8 = 16320 parts called fragments.
	+
	+	The binary format is simply uint64_t[16320].
	+
	+	We don't care about endianness, but it has to be the same on all of your devices. As you are probably using amd64, it is little endian.
	+
	+	===== clblob data format =====
	+
	+	clblob is submitted by userspace library (oclvankus) to the computing kernel (slice.c), then computing is carried and the result is pushed from the kernel back to oclvankus.
	+
	+	Each fragment in the clblob is specified by uint64_t[4].
	+
	+	<code>struct frag {
	+	uint64_t prng; // cipher internal state
	+	uint64_t rf; // constant that is XORed in after each round
	+	uint64_t challenge; // cipher state we are hunting for
	+	uint64_t flags;
	+	}</code>
	+
	+	Flags:
	+
	+	0x01 = End of color (i.e., 12 bits zero) reached
	+
	+	0x02 = Challenge found, the secret cipher state is in frag.prng.
	+
	+	===== "return" messages =====
	+
	+	Once the client submits a job (114 bits of A5/1 keystream) using the "crack" command, job number is assigned by the server. This is reported as "Cracking #<job_number> <keystream_again>".
	+
	+	If the secret state is found, a message is generated: "Found <secret_state_in_hexadecimal> @ <position> #<job_number> (table:<table_id>)".
	+
	+	Once the job is finished (all fragments have been computed), "took" message is generated: "crack #<job_number> took <number> msec".
	+
	+	These messages are sent to all clients that have submitted a "crack" command.
	+
	+	===== "stats" message =====
	+
	+	The client can enter "stats" command. The server prints how many bursts are queued in which stage of cracking.
	+	<code>
	+	submitted: N
	+	dpsearch: N
	+	endpoints: N
	+	startsearch: N
	+	startpoints: N
	+	collsearch: N
	+	finished: N
	+	</code>

project:gsm:deka:deka-test

Anonymous (anonymous@undisclosed.example.com) — 2016-09-28T07:41:24+00:00

1463000720	current
Line 1:	Line 1:
	+	Also, [[http://jenda.hrach.eu/brm/kraken_magic/bursts.samplesession.tgz\|here]] (17 MB) are 100 computed and then looked-up bursts using Berlin table set. You can turn on debug in vankusconf.py, run the same cracking and binary compare them.

	+	<note warning>We have now discovered that a few fragments might be broken there due to the bug that was fixed in commit [[https://jenda.hrach.eu/gitweb/?p=deka;a=commit;h=a0e62597948bfa6f874d852baea3411e651c48ca\|a0e6259]]. Somebody should recompute it…</note>
	+
	+	<code>
	+	crack 001110001001010111000110000100110100001000011010100001000010000110101100101010100110110100100111110011101110000000
	+	Found 44D85D82BAF275B4 @ 2 #0 (table:412)
	+	crack 110001101011011010010110100001100111010100010011100000110011111100111110111011110111101100100111110100010110110000
	+	Found 85C010A0C8190CAD @ 50 #1 (table:500)
	+	crack 011010110100111011110001111111001110000111111110101101110001010001110000100111100010100001000001001000110001000101
	+	Found C567E87DFAF8EDC2 @ 26 #2 (table:204)
	+	Found A0A6C860F4002A2F @ 50 #2 (table:356)
	+	Found FA4C760AD5B8C4C0 @ 0 #2 (table:220)
	+	crack 101010011100110110011101111011010101100110111010000001100100111001101101110010100001001101101100000001111110101101
	+	Found 670D3F982B23E212 @ 10 #3 (table:230)
	+	Found 6DCE143EFE01267B @ 35 #3 (table:268)
	+	crack 100000101010010110101100001111110011110110000000010111011111001110110110100111111100010000111100100001110000110000
	+	Found D8EC7C056AEF42B2 @ 4 #4 (table:340)
	+	crack 100000011000000011000101101110100010001100101010101111110001011111100100011100001000110000101101000110011101000011
	+	Found D18F7BEC02CE3CC1 @ 16 #5 (table:404)
	+	crack 010000111011001100010100001011011110110000001010100010001001000000100111110101011000011010000010001100000010110000
	+	Found 7DBD3987DF029917 @ 32 #6 (table:404)
	+	crack 110010011100001101110111001110110100011011000111010110111011011000101010001111010100001100111010101100001011111101
	+	Found 9F995DF5C129BBC1 @ 21 #7 (table:372)
	+	crack 100001000010100001111101001010111111110100010111101011110101111011011011000111110001010010001110000001000101111100
	+	Found 6E6B7CF056EF1160 @ 13 #8 (table:180)
	+	crack 111110100100010110011101010001001111111011111000001011110110110000111110010001001111000100011111010101000111000101
	+	Found 3085C1F782480AF2 @ 23 #9 (table:332)
	+	crack 100101000101001011001000111110000000011111111000001001000100011001010010101011110111100111100100010100000010010101
	+	Found 806490FBC9EF5D3F @ 24 #10 (table:332)
	+	crack 110000111101111011011100000111011000010010011010101010110010100010010101010101000110010101011010101000101001000000
	+	Found 70A4DF79902565E4 @ 20 #11 (table:196)
	+	crack 100000000011011011010101010100100101101110000000100100010101000110011111100010111101010110011000100100111110100100
	+	Found 5674A61F7B6290C2 @ 27 #12 (table:412)
	+	crack 100111110101101111110001010010001110110000110011010001101111110101100100000001000100100011100001110010111111000000
	+	Found E179A1F7B213005F @ 17 #13 (table:268)
	+	crack 101011100010100000110010010001001001001001001011111111001001001100101000111111110110110111011000100000101110000000
	+	Found 8A5F47787DB56D3D @ 43 #14 (table:100)
	+	crack 011111100010011010000110001001001001001111100001000100111000001011011010000111001000000001001000101001111001011010
	+	Found AA454F400A859C43 @ 16 #15 (table:132)
	+	crack 111010110001001001001101011110011101001111000010100011100111000111010100011001111010000111110101100011111100111000
	+	crack 111001110000101111100110010101000010111100011011111011101101101101001000111111001110011011000000000101000101110110
	+	Found E593DA1F71D97084 @ 33 #17 (table:428)
	+	</code>
	+
	+	A find_kc downlink test vector:
	+	<code>
	+	> find_kc A53F8FC39DD1A817 46 377760 377753 010010011100000010110100111001000010011110001011000001100111111010001101111100011110010001011001111100010011111101
	+	#### Found potential key (bits: 46)####
	+	5e7d56d51026541b -> 5e7d56d51026541b
	+	Framecount is 377760
	+	KC(0): a9 2b 0c c2 fb e9 f2 be mismatch
	+	KC(1): e9 14 78 14 23 32 ea 9e mismatch
	+	KC(2): f6 88 19 c5 3c f0 6e 1c * MATCHED *
	+	KC(3): 44 ce bc 15 c2 1c 96 6c mismatch
	+	KC(4): 74 83 57 47 3e 52 dc bf mismatch
	+	KC(5): f3 d2 bf b1 6f 39 c7 9c mismatch
	+	KC(6): fa 66 be 6e ad 6c 2c 6e mismatch
	+	KC(7): 8d 79 16 c8 c4 45 ba 8a mismatch
	+	KC(8): c6 e9 4a 01 3e 7f 14 84 mismatch
	+	</code>

Deka - an OpenCL A5/1 cracker

Anonymous (anonymous@undisclosed.example.com) — 2022-03-25T19:42:56+00:00

1508559698		current
Line 34:		Line 34:
	TL;DR You can go through the A5/1 keyspace and save some "distinguished points". When you want to recover the key, you reconstruct the keyspace from the nearest distinguished point. ([[attack-theory\|I want to know more!]])		TL;DR You can go through the A5/1 keyspace and save some "distinguished points". When you want to recover the key, you reconstruct the keyspace from the nearest distinguished point. ([[attack-theory\|I want to know more!]])

-	Deka listens on a TCP socket, waits for a keystream and once you submit one, it finds a secret state that resulted in this keystream. Hence you need some GSM sniffer, keystream guesser, TCP client and secret state processor. [[:user:jenda:gsm\|gsmtk]] implements exactly that.	+	Deka listens on a TCP socket, waits for a keystream and once you submit one, it finds a secret state that resulted in this keystream. Hence you need some GSM sniffer, keystream guesser, TCP client and secret state processor. [[https://jenda.hrach.eu/w/gsm\|gsmtk]] implements exactly that.

	Recommended configuration:		Recommended configuration: