Randomart và thuật toán The Drunken Bishop

Bài viết được sự cho phép của tác giả Huỳnh Quán Cẩm

Khi tạo OpenSSH key ta hay bắt gặp một cái hình tên là randomart.

The key's randomart image is:
+---[RSA 2048]----+
|   .  o.+.       |
|  o .. +..       |
| o o. ... .      |
|. =  . =..       |
|.o.o  o.S .      |
| +. o  +.o o     |
|. oo..+o= o .    |
| +...o=*o= .     |
|o......EB        |
+----[SHA256]-----+

Có bao giờ bạn thắc mắc hình này dùng để làm gì không?

1. randomart là gì?

Khi tạo kết nối SSH tới một host nào đó, OpenSSH sẽ yêu cầu host đó cung cấp RSS key fingerprint.

$ ssh host.xyz
RSA key fingerprint is SHA256:nThbg6kXUpJWGl7E1IGOCspRomTxdCARLviKw6E5SY8.

Fingerprint này được dùng để xác thực host. Điều bạn cần làm với fingerprint này là kiểm tra xem nó có trùng với key của host đích mà bạn đang kết nối tới hay không. Trùng thì không có gì để bàn rồi. Còn không trùng thì … rất có khả năng bạn đang bị tấn công MiTM.

Nhưng những fingerprint này thường là những chuỗi vô nghĩa. Cách để so trùng những chuỗi này là … so trùng từng chữ bằng mắt. Chúa tạo ra con người hoàn hảo tuyệt đối. Trừ cặp mắt thôi. Điểm mù, saccades, đủ thứ cả. Chưa kể còn sai sót nữa. Bắt tui ngồi so những chuỗi dạng nThbg6kXUpJWGl7E1IGOCspRomTxdCARLviKw6E5SY8 cả ngày, thà bỏ nghề đi làm cách mạng còn hơn.

Vì vậy, randomart được sinh ra nhắm giải quyết bài toán này. Nó trực quan hóa những chuỗi vô nghĩa thành hình ảnh. Từ những hình ảnh này, người dùng có thể nhanh chóng phán đoán được độ đúng đắn của host key.

Đồng thời những hình ảnh này có thể sẽ rất khác nhau cho dù fingerprint của chúng chỉ lệch nhau một chút. Từ đó giúp giảm thiểu sai sót của user người truồng mắt trần.

Randomart của fingerprint ở trên có hình dạng như dưới. Để thấy hình randomart, bạn cần bật VisualHostKey=yes trong SSH config.

$ ssh host.xyz
RSA key fingerprint is SHA256:nThbg6kXUpJWGl7E1IGOCspRomTxdCARLviKw6E5SY8.
+---[RSA 2048]----+
| =+o...+=o..     |
|o++... *o .      |
|*.o.  *o.        |
|oo.  ..o.= .     |
|.+o. .. S =      |
|*=+ .  o = .     |
|OE .  . o        |
| o     .         |
|                 |
+----[SHA256]-----+
Are you sure you want to continue connecting (yes/no)?

Nếu bạn chưa nhận ra, đây là host key của Github . Nếu một ngày pull code từ Github về mà không thấy hình ảnh quen thuộc này, tui sẽ lập tức đánh hơi được sự bất thường. Cách mạng đã tràn về như một cơn sóng rồi sao?

Randomart được tạo ra từ một thuật toán sặc mùi bia rượu: The Drunken Bitshop (tạm dịch: Say quắc ông giám mục).

2. Thuật toán

Thuật toán được tóm gọn trong một đoạn văn như sau:

Bishop Peter finds himself in the middle of an ambient atrium. There are walls on all four sides and apparently there is no exit. The floor is paved with square tiles, strictly alternating between black and white. His head heavily aching—probably from too much wine he had before—he starts wandering around randomly. Well, to be exact, he only makes diagonal steps—just like a bishop on a chess board. When he hits a wall, he moves to the side, which takes him from the black tiles to the white tiles (or vice versa). And after each move, he places a coin on the floor, to remember that he has been there before. After 64 steps, just when no coins are left, Peter suddenly wakes up. What a strange dream!

tạm dịch: Giám mục Peter đang ở giữa một cái sảnh với bốn mặt tường. Vang vọng là tiếng hát Khánh Phương với bài “Không lối thoát”. Sàn nhà lót bằng gạch trắng đen hình vuông. Đầu ổng rất nhức. Hẳn rồi, tối qua quắc quá mà. Ổng bắt đầu đi loạng choạng. Chính xác thì ông chỉ đi những bước xéo như con tượng trên bàn cờ vua. Khi đụng tường, ông đi một bước ngang hoặc dọc. Điều đó giúp ông chuyển từ ô đen sang ô trắng và ngược lại. Sau mỗi bước, ông đều đánh dấu lãnh thổ bằng cách đái một bãi đặt một đồng xu lên sàn, để ghi nhớ là ông đã đi qua đó rồi. Sau 64 bước, không còn đồng xu dính túi, Peter đột nhiên tỉnh dậy. Quả là một giấc mơ vế lù.

2.1. Bắt đầu

Thuật toán khá đơn giản, Peter cũng bắt đầu từ chính giữa phòng, kí tự hiệu là ‘S’.

1111111
01234567890123456
+-----------------+x (column)
0|                 |
1|                 |
2|                 |
3|                 |
4|        S        |
5|                 |
6|                 |
7|                 |
8|                 |
+-----------------+
y
(row)

2.2. Di chuyển

Giám mục Peter có thể di chuyển theo 4 hướng: , , , , ứng với từng cặp bit của fingerprint.

bits	hướng
00
01
10
11

Bắt đầu với một fingerprint dạng MD5 với các octet a1:b2:c3:d4:e5:f6:...:e1. Ta tiến hành dịch nó từ HEX sang binary như sau:

10100001:10110010:11000011:...:11100001

Đọc theo Little Endian, nó sẽ thành:

01 00 10 10 : 10 00 11 10 : ... : 01 00 10 11

Áp dụng với bảng ở trên, các bước đầu tiên của giám mục Peter lần lượt là:      . Dấu chấm tượng trưng cho những điểm mà ổng đã đi qua.

1111111
01234567890123456
+-----------------+x (column)
0|                 |
1|                 |
2|        .        |
3|       . .       |
4|    . . S        |
5|     .           |
6|                 |
7|                 |
8|                 |
+-----------------+
y
(row)

Đụng tường

Như đã mô tả, khi đụng tường Peter sẽ đi ngang hay dọc tùy theo hướng.

Giả sử ông ta đang ở vị trí 0-4 (x-y), và hướng tiếp theo của chúng ta là , giám mục sẽ đi .

1111111
  01234567890123456
+-----------------+x (column)
0|                 |
1|                 |
2|        .        |
3|.      . .       |
4|.   . . S        |
5| . . .           |
6|  .              |
7|                 |
8|                 |
+-----------------+
y
(row)

2.3. Đánh dấu

Để đánh dấu, ứng với số lần mà ô đó được đi qua, ta sẽ dùng các kí hiệu sau.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
  . o + = * B O X @  %  &  #  /  ^  S  E

Nếu ô đó được đi qua 7 lần, ta sẽ đánh O, 11 lần sẽ đánh &, S là ô bắt đầu và E là ô kết thúc.

Và cứ như thế, một hình ảnh randomart đã được tạo ra.

3. Tham khảo

Các bạn có thể tham khảo về thuật toán tại paper The drunken bishop: An analysis of the OpenSSH fingerprint visualization algorithm.

4. Bài viết này sẽ giúp tui tăng lương như thế nào?

Như thường lệ bài viết không có giúp bạn tăng lương. Cơ mà có một số điều rút ra là:

1. Luôn kiểm tra host key khi kết nối SSH, để lỡ có ăn hành thì cũng biết đường mà … đánh răng.
2. Bật VisualHostKey=yes trong SSH config để kiểm tra bằng hình ảnh thay vì bằng chuỗi.

Bài viết gốc được đăng tải tại quan-cam.com

Có thể bạn quan tâm:

• Thuật toán Quy hoạch động – một thuật toán thần thánh
• Các thuật toán sắp xếp phổ biến và JavaScript
• Thuật toán là gì? Lập trình viên có cần biết thuật toán không?

Xem thêm các việc làm Developer hấp dẫn tại Station D