Điểm:0

Thuật toán Grover cho AES ở chế độ CBC

lá cờ in

Xin chào,
Tôi đã tự hỏi liệu về mặt lý thuyết có thể sử dụng thuật toán Grover để phá vỡ AES trong chế độ CBC hay không. Giả sử rằng tôi có ~1000 cặp bản rõ/bản mã và độ dài khóa là 128 bit. Tôi nghĩ về nó theo cách này:

  1. Đối với mỗi cặp bản rõ và bản mã, chỉ sử dụng 16 byte đầu tiên của bản rõ và 16 byte đầu tiên của bản mã. (Chúng sẽ được dán nhãn là PN, CN trong đó n là cặp thứ n)
  2. Viết tập hợp các phương trình với một biến chưa biết - khóa. (Khóa được dán nhãn là K)
    AES-128đ(C1, K) â AES-128đ(C2, K) = P1 â P2
    AES-128đ(C3, K) â AES-128đ(C4, K) = P3 â P4
    AES-128đ(C5, K) â AES-128đ(C6, K) = P5 â P6
    ...
    AES-128đ là chức năng giải mã AES-128
    â là XOR
  3. Sử dụng thuật toán Grover để tìm K từ các phương trình đã cho ở trên. Nếu khóa được tìm thấy, việc xác định IV rất dễ dàng bằng cách sử dụng phương trình này:
    AES-128đ(C1, K) = P1 â IV

Thuật toán Grover có thể được sử dụng để đảo ngược tập hợp các phương trình từ bước 2 không? Tôi cần bao nhiêu cặp bản rõ/bản mã để xác định duy nhất khóa và IV cho độ dài khóa 128, 192 và 256 bit?

Điểm:0
lá cờ my

$\text{AES-128}_d(C_1, K) \oplus \text{AES-128}_d(C_2, K) = P_1 \oplus P_2$

Điều đó không cho rằng hai bản mã có chung IV sao? Thông thường, họ không.

Trong mọi trường hợp, ngay cả khi bạn không biết bất kỳ IV nào, thì một phương pháp đơn giản hơn sẽ là nếu bạn có một thông báo hai khối đã biết với văn bản gốc $(P_a, P_b)$ và một bản mã tương ứng $(C_a, C_b)$, sau đó

$$\text{AES-128}_e(P_b \oplus C_a, K) = C_b$$

Điều này giữ bất kể IV đã được sử dụng.

Thuật toán Grover có thể được sử dụng để đảo ngược tập hợp các phương trình từ bước 2 không?

Tôi giả sử. Tuy nhiên, nếu tất cả những gì bạn có là một loạt các thông báo khối đơn lẻ, thì bạn phải giả định rằng tất cả các IV đều giống nhau. Nếu chúng không xác định và ngẫu nhiên, thì bạn không thể suy luận bất cứ điều gì.

pajacol avatar
lá cờ in
Tôi nên làm rõ rằng ý tôi là các IV thực sự giống nhau và tôi chỉ biết 16 byte đầu tiên của mỗi văn bản gốc.
Điểm:0
lá cờ us

Thuật toán của Grover sẽ hoạt động với CBC. Bạn có nghĩa là bạn có vài nghìn tin nhắn văn bản gốc/bản mã, mỗi tin nhắn có IV riêng?

Tôi không chắc bạn đang làm gì ở bước 2. Tôi nghĩ nói chung IV được coi là một phần của bản mã, vì vậy nếu bạn có bản mã, bạn có IV, và sau đó bạn có các phương trình như:

AES-128$_d$(C$_1$, K) = IV $\oplus$ P$_1$

AES-128$_d$(C$_2$, K) = C$_1 \oplus$ P$_2$

vân vân.

Đối với thuật toán Grover, vì bạn biết vế phải và bạn biết đầu vào của quá trình giải mã AES, nên bạn có thể tìm kiếm trong không gian của K và đối với lời tiên tri, hãy sử dụng một mạch để thực hiện giải mã AES của C$_1$, C$_2$, v.v. và so sánh với giá trị ở vế phải.

Để gần như chắc chắn rằng giá trị trả về K là đúng, bạn chỉ cần 2 khối cho AES-128 (tức là chỉ C$_1$ và C$_2$ của một tin nhắn), 2 khối cho AES-192 và 3 khối cho AES-256. Nói chung, nếu bạn sử dụng $r$ khối, mỗi khối có $n$ bit và với một khóa của $k$ bit, xác suất tìm kiếm của Grover sẽ tìm thấy khóa chính xác là khoảng $e^{-2^{k-rn}}$. Vì thế nếu $k < rn$, về cơ bản bạn được đảm bảo kết quả chính xác (xem phần "Khóa giả mạo" trên trang 4 của tờ giấy này cho một dẫn xuất).

pajacol avatar
lá cờ in
Ý tôi là các IV giống nhau và tôi chỉ biết 16 byte đầu tiên của mỗi văn bản gốc nhưng số lượng các cặp 16 byte này là khoảng 1000.
Sam Jaques avatar
lá cờ us
À, vậy là bạn chỉ có thể kiểm tra AES-128$_d$(C$_1$, K)=IV$\oplus$ P$_1$ cho mỗi tin nhắn. Tôi nghĩ rằng câu trả lời của tôi sẽ giống nhau, nhưng bạn sẽ sử dụng C$_1$/P$_1$ từ 2 hoặc 3 trong số các cặp 16 byte.

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.