Chia sẻ Dumv 21/03/2025 0 Comments

Stream Cipher Phần 1 – LFSRs

Bài viết hôm nay mình sẽ giới thiệu về những stream cipher sử dụng LFSR làm PRNG chính, như CSS hay E0.

Table of Contents

Linear Feedback Shift Register

Trong bài viết trước về PRNG, ta đã bàn sơ lược cách thức hoạt động của LFSR. Nhưng về mặt lý thuyết, phép toán sử dụng không cần phải là phép XOR, nó có thể là phép toán tuyến tính – linear nào. Tính chất linear này của LFSR lại là một điểm yếu nghiêm trọng, hay được khai thác trong cryptanalysis. Ta sẽ bàn sâu về vấn đề này sau.

Trở lại phân tích cơ chế hoạt động của LFSR, ta sẽ dùng lại ví dụ ở bài viết trước.

Cho seed = 01101001

Ta sẽ chọn 3 vị trí trong seed trên: Vị trí thứ 2, 5, và 7. Những vị trí này được
gọi là tap. Như vậy, rõ ràng output sẽ phụ thuộc vào tap.

Ta XOR những bit của seed ở những tap:
seed[2] xor seed[5] xor seed[7] = 1 xor 1 xor 0 = 0

Sau đó ta "đẩy" bit 0 này lên đầu seed, làm "rớt" bit cuối: 00110100. Đây là output
của chúng ta.

Ta lại có thể tiếp tục thực hiện thuật toán nếu ta không ưng ý với output.

Tất nhiên, vì đây đơn thuần chỉ là PRNG, nên đến một lúc nào đó, ta sẽ thu lại 1 output cũ. Vì vậy, trên thực tế, việc chọn đúng các tap là rất quan trọng, vì chúng quyết định vòng lặp là dài hay ngắn. Vòng lặp càng dài, sẽ càng mất thời gian hơn để phá PRNG. Một ví dụ tiêu biểu là Fibonacci LFSR, hoạt động trên chuỗi 16 bit, với các tap (1, 11, 13, 14, 16) sẽ cho ra 65535 (2¹⁶ – 1) output khác nhau, là chu kì lớn nhất có thể.

Đây là biểu diễn output của Fibonacci LFSR, tap (28, 31) trên bảng mạch điện tử: Link

Còn đây là code C++ của Fibonacci LFSR:

int fibLFSR(int seed) {
    //seed != 0
    int lfsr = seed; //lfsr là output
    int bit = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5)) & 1;
    lfsr = (lfsr >> 1) | (bit << 15);
    return lfsr;
}

Với những phép toán như trên, chỉ có XOR và dịch bit, implement LFSR trên hardware rất dễ và hiệu quả.

Thế nhưng không chỉ dừng lại ở đó, có nhiều thuật toán LFSR nhanh hơn, hiệu quả hơn mà vẫn đảm bảo vòng lặp là dài nhất có thể.

Sau đây là 2 code để thực hiện Galois LFSR đối với các chuỗi nhị phân độ dài 16 tại các tap (1, 11, 13, 14, 16), vòng lặp cũng có chu kì 65535:

int galoisLFSR1(int seed) {
    int lsb = lsb(seed); //trả về bit cuối của seed
    int lfsr = seed;
    lfsr >>= 1;
    if (lsb) lfsr ^= 46080;
    /* 46080 (dec) = 1011010000000000 (bin), các bit 1 ở các tap 11, 13, 14, 16 
(đếm từ phải sang) */
    return lfsr;
}
int galoisLFSR2(int seed) {
    int msb = msb(seed); //trả về bit đầu của seed
    int lfsr = seed;
    lfsr <<= 1;
    if (msb) lfsr ^= 45;
    // 45 (dec) = 0000000000101101 (bin), các bit 1 ở các tap 11, 13, 14, 16
    return lfsr;
}

Ngoài ra, sau đây là thuật toán khác, Xorshift, cũng đối với chuỗi nhị phân 16, cho ra chu kì dài nhất:

int xorshift(int seed) {
    int lfsr = seed;
    lfsr ^= lfsr >> 7;
    lfsr ^= lfsr << 9;
    lfsr ^= lfsr >> 13;
    return lfsr;
}

Vì về mặt tính toán, Galois LFSR và Xorshift gồm ít phép toán hơn LFSR đầu tiên, chúng chạy hiệu quả hơn trên software.

Tuy nhiên, việc có chu kì dài nhất mới chỉ là điều kiện cần thôi, chưa phải là đủ. Như đã nêu trên, vì LFSR chỉ đơn thuần thực hiện các phép XOR và dịch bit, ta có thể dễ dàng tìm ra seed nếu có được output.

Vì thế, trong thực tế, những stream cipher dùng LFSR làm PRNG trụ cột sẽ không chỉ dùng LFSR thuần túy trong code của nó. Đến đây, ta sẽ phân tích cách một số stream cipher sử dụng LFSR cũng như tăng độ bảo mật cho keystream.

Các stream cipher sử dụng LFSRs

Chủ yếu vì tính đơn giản và hiệu quả của LFSR trong hardware nên mới được đưa vào sử dụng nhiều trong stream cipher trước khi phát triển software. Những stream cipher LFSR thông dụng là:

CSS (Content Scramble System) trong mã hóa DVD – 2 LFSRs
A5/1, A5/2 trong các cục gạch hãng GSM – 3 LFSRs
E0 trong phương thức của Bluetooth – 4 LFSRs

Những cipher này đều đã bị phá tanh bành và không còn được sử dụng nữa.

Cơ chế hoạt động

Trước hết, chúng ta sẽ phân tích cách thức hoạt động chung của những cipher này. Với mục tiêu là làm tăng tính ngẫu nhiên từ keystream có tính chất “tuyến tính”, ta có thể đưa thêm các phép toán khác vào, nhưng vẫn phải đảm bảo thời gian sinh keystream tăng không đáng kể.

Đối với CSS, key ban đầu chỉ gồm 5 byte (40 bit) vì những giới hạn về xuất khẩu
hardware. Ở đây ta lấy ví dụ key = 1000010111111000110011101001100010101001

CSS gồm 2 LFSR. LFSR 1 gồm 17 bit: 11000010111111000
(bit 1 ghép với 16 bit đầu của key.)
LFSR 2 gồm 25 bit: 1110011101001100010101001
(bit 1 ghép với 24 bit sau của key.)

Ta thực hiện LFSR lên 2 chuỗi bit đó (có thể vài lần), sau đó lấy 8 bit (byte) cuối
của mỗi chuỗi, thực hiện phép cộng modulo 256 trong hệ thập phân. Từ đó ta được 1 byte
của keystream.
Như vậy, giả sử output đầu tiên của 2 LFSR lần lượt là 11100001011111100 và
0111001110100110001010100, có được 2 byte tương ứng là 11111100 (252) và 01010100 (84).
Thực hiện phép cộng modulo 256 2 byte đó sẽ cho ra 80, tức byte 01010000, byte đầu
tiên của keystream. Ta tiếp tục thực hiện LFSR với 2 chuỗi lớn trên, lấy byte cuối của
từng chuỗi và cộng lại để thu được các byte tiếp theo.

Có một cơ chế hoạt động sử dụng 3 LFSRs và 1 hàm boolean. Input của hàm bool sẽ là LFSR thứ 3. Nếu input là bit 0 thì sử dụng LFSR thứ 1, còn bit 1 thì sử dụng LFSR thứ 2.

Trong cryptanalysis

Tuy nhiên, tất cả những cách implement này đều đã bị reverse engineer, như những stream cipher LFSR khác, và bị phá nhanh chóng. Tệ hơn, đối với nhiều cipher như CSS, ta chỉ cần tìm ra một LFSR là đã có thể tìm ra tất cả các LFSR còn lại.

Đây là một tấn công lên Content Scramble System mà các bạn có thể làm tại nhà.

Cho là ta có encryption của 1 cái DVD được mã hóa bằng CSS (ciphertext), và ta
cần phá nó. Trước hết, ta biết định dạng file của DVD, mà thông thường thì vài
byte đầu của một định dạng file sẽ cố định. Vậy cứ cho là ta biết 20 byte đầu của
file rồi (plaintext).

Ta XOR 20 byte đầu của ciphertext với plaintext lại thì sẽ được 20 byte đầu của
keystream.

Đến đây thì ta sẽ brute force tất cả 2^17 chuỗi nhị phân 17 để tìm ra LFSR số 1.
Từ đó, do keystream bằng LFSR 1 cộng mod 256 với LFSR 2, ta chỉ cần lấy keystream
trừ mod 256 LFSR 1 để ra được LFSR 2, từ đó có được cả key 40 bit và phá cả cái DVD.