Quần Cam Blog

Randomart và thuật toán Ông giám mục say xỉn

#til #ssh #algorithm

MỤC LỤC

Khi tạo OpenSSH key ta hay thấy một cái như vậy.

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]-----+

Tò mò không biết nó là gì, google một hồi thì biết nó tên là randomart, và có cả một thuật toán sau lưng nó.

1. randomart là gì?

Khi kết nối tới một host, OpenSSH thường cho bạn biết RSA key fingerprint của host đó. Bạn sẽ dùng nó để xác minh với chủ host xem fingerprint đúng hay không. Đúng thì kết nối, còn không thì rất có khả năng … bạn đang bị tấn công MiTM (man in the middle).

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

Nhưng so trùng chuỗi bằng mắt thường thì không tốt cho mắt lắm và dễ sai, nên randomart được sinh ra.

Randomart là một cách để hình ảnh hóa (visualize) một cái fingerprint, từ đó người dùng có thể dùng hình ảnh này để kiểm tra sự đúng đắn của host key.

Nếu có bật VisualHostKey=yes trong SSH config, bạn sẽ xem được randomart của host.

$ ssh host.xyz
The authenticity of host 'host.xyz (192.30.253.113)' can't be established.
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)?

Vì đã biết randomart của host.xyz trước đó, nên nếu hình ảnh lúc này lệch qua phải thay vì qua trái, mình sẽ ngay lập tức biết có gì đó không đúng.

Randomart của OpenSSH được tạo ra từ thuật toán Ông giám mục say xỉn (The Drunken Nishop) mà mình sẽ nói ở dưới.

2. Thuật toán

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 thấy ông ta đang ở giữa một cái sảnh với bốn mặt đều có tường và không có lối thoát. Sàn nhà được lót bằng gạch trắng đen hình vuông. Đầu ông ta rất nhức, chắc do uống quá nhiều rượu trước đó, nên ông bắt đầu đi lung tung. Chính xác thì ông chỉ đi những bước xéo như con pháo trên bàn cờ vua. Khi đụng tường, ông đi một bước ngang hoặc dọc, nhờ đó giúp ông chuyển từ ô đen sang ô trắng hoặc ngược lại. Sau mỗi bước, ông đều đặt một đồng xu lên sàn để ghi nhớ là ông đã đi qua đó rồi. Sau 64 bước, khi không còn đồng xu nào cả, Peter đột nhiên tỉnh dậy. Quả là một giấc mơ kì lạ.

2.1. Bắt đầu

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

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

2.2. Di chuyển

Ông giám mục có thể đi theo 4 hướng:

  • “00” - 1 bước hướng ↖️
  • “01” - 1 bước hướng ↗️
  • “10” - 1 bước hướng ↙️
  • “11” - 1 bước hướng ↘️

Ví dụ ta có một host key là có fingerprint dưới dạng MD5 là a1:b2:c3:d4:e5:f6:...:e1. Dịch từ HEX sang binary sẽ là:

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ào thuật toán trên, các bước của đầu tiên của ông giám mục sẽ lần lượt là ↗️ ↖️ ↙️ ↙️ ↙️ ↖️.

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

Đụng tường

Như câu chuyện của thuật toán đã mô tả, nếu đụng tường ông giám mục 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ư thuật toán mô tả, ông giám mục để để lại đồng xu để đánh dấu những ô ông ta đã đi qua. Vậy ta sẽ đánh dấu thế nào?

Ứ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.

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ờ câu hỏi này mà mình bán được cũng kha khá tiền bản quyền, và như thường lệ mình không có giúp bạn tăng lương. Cơ mà có một số điều rút ra là:

  1. Đừng xỉn … mệt lắm :(.
  2. Luôn kiểm tra host key khi kết nối SSH, mình cũng yes :(.
  3. Bật VisualHostKey=yes trong SSH config để kiểm tra host.
  4. Like trang này để giúp mình tăng lương :troll:.

Bài viết cùng chủ đề

How to explain rsync to a six year old

What would be the easiest way to explain how rsync works to a six year old?

Monitor Varnish Cache như thế nào?

Varnish Cache là một HTTP reserve proxy giúp tăng tốc web và giảm tải cho backend server của bạn. Bài viết này giới thiệu một số điểm cần chú ý khi monitor Varnish.

Code Đức

Là một developer tất nhiên bạn phải chuyên nghiệp với nghề của mình. Thế nhưng chuyên nghiệp là như thế nào? Và bạn, một developer, sẽ phải hành xử ra sao mới được xem là chuyên nghiệp?