Deadline 04.10.2024 08:00

Files (1.bin, 2.bin, 3.bin, 4.bin, 5.bin) were generated using following commands:
	python3 LCG.py -m 2**31 -a 1103515245  -c 12345 -l 0  -u 31 -n 10000 --file 4.bin				
	python3 LCG.py -m 2**48 -a 25214903917 -c 11    -l 16 -u 47 -n 10000 --file 1.bin
	dd if=/dev/urandom of=3.bin bs=4 count=10000
	openssl rand -out 2.bin 40000
	rand_file.c =>  compile => ./a.out 5.bin    (HINT: https://www.mathstat.dal.ca/~selinger/random/) 

Identify the generator and provide the mapping:
1.bin <=> name2 (-m 2**48 ... )
2.bin <=> name4 (openssl rand)
3.bin <=> name3 (dev/urandom)
4.bin <=> name1	(2**31)
5.bin <=> name5  (C rand)


Explain how you identified the files. If it is not possible to identify the source explain why.


How to identify the sources: 
1. Sources openssl rand, dev/urandom are cryptographically secure TRNG and do not (if implemented properly) produce patterns. Hence these sources are indistinguishable and can not be identified. 
2. Based on provided hint, the source rand_file.c can be identified using the linearity: o_i = o_{i-31} + o_{i-3} mod 2^{31} or  o_i = o_{i-31} + o_{i-3} + 1 mod 2^{31}. Similarly to the next LCG -m 2**31 it produces data with fixed (0) most significant bit. 
3. The first LCG produces easily identifieable pattern - msb bit in 32-bit blocks is always 0 since this generator produce only 31 bit blocks. 
4. The second LCG (-m 2**48) can be identified by brutte-force. The internal state has 48 bits but generated values consists of only 32 bits. In the brutte-force attack we can iterate through all possible 16 bits and try to reconstruct internal state - for correct state next random values will correspond.

Other approach for all PRNG is to brute-force the seed. In order to optimize the computation one should start with the time when the assignment was published and go backward. Also, many of you computed the entropy of the files which may help to distinguish the sources but as a single metrics is not sufficient!