演算法漫談 - Padding 填充如何表示原始資料長度?
3 |
在演算法中常有將原始資料補到固定長度的需求,例如:Base64 編碼是將三個 Byte 資料轉成四位英數字加 +、/ 符號(大寫x26 + 小寫x26 + 數字x10 + 符號x2 = 64 = 26,四個字元 4 x 26 == 3 x 28 三個Byte),若資料 Byte 數非 3 的倍數就要補零到所需長度。而 AES 加密計算區塊以 128 bits 為處理單位,DES 區塊大小則是 64 bits,不同長度原始資料必須補足 16 Bytes 或 8 Bytes 整數倍再進行運算。
題外話:最近 Base64 編碼上了新聞,臺中市警察局提供交通違規檢舉資料出包(身分證未加密烏龍!臺中市警察局公布檢舉達人個資遭洩露),承辦人員不知缺少相關知識還是故意裝糊塗,竟把 Base64 編碼當馬賽克用,讓檢舉人身分證號穿著國王新衣遊街。殊不知這跟當年第四台鎖碼成人頻道一樣,懂門道弄支解碼棒,人人能看。而 Base64 解碼棒更是唾手可得,在瀏覽器按 F12 用一行指令 atob('QTEyMzQ1Njc4OQ==')
即可破解...
補零的一項挑戰是必須記錄或辨別原始資料長度,否則還原時會搞不清楚最後一個區塊哪些是原始資料,哪些是填充物。
Base64 採用的做法是填充部分用 64 個字元之外的符號「=」來表示,資料三個 Bytes 為單位,若結尾有兩個 =,表示資料長度除 3 的餘數為 1;若結尾有一個 =,則表除 3 餘數為 2:
換到 AES 或 DES byte[16]/byte[8] 填充的場景,byte 0 - 255 每一個都可能是有效資料,無法像 Base64 找 64 個字元之外的符號表示。一個無腦解法是在資料前方加個長度欄位,用幾個 Byte 記錄長度,但資料結構跟處理邏輯會因此複雜化,不夠優雅。但是,若不這麼做,原始資料有無限多種可能,就是會遇到跟填補樣式一模一樣的組合,讓你分不出是長度不足填補過的內容,還是長度剛好內容雷同的原始資料。
問題看似無解,其實前人早就想到巧妙解法。以 PKCS #5: Password-Based Cryptography Specification Version 2.0 為例,它採用的填充規則如下:(註:另有 PKCS #7,原理相同,但區塊長度支援 1 ~ 255 Bytes)
Concatenate M and a padding string PS to form an encoded message EM:
EM = M || PS ,
where the padding string PS consists of 8-(||M|| mod 8) octets
each with value 8-(||M|| mod 8). The padding string PS will
satisfy one of the following statements:
PS = 01, if ||M|| mod 8 = 7 ;
PS = 02 02, if ||M|| mod 8 = 6 ;
...
PS = 08 08 08 08 08 08 08 08, if ||M|| mod 8 = 0.
The length in octets of the encoded message will be a multiple
of eight and it will be possible to recover the message M
unambiguously from the encoded message. (This padding rule is
taken from RFC 1423 [3].)
若要補足 8 Bytes,當長度除 8 餘 7,補 01;除 8 餘 6 補 02 02;除 8 餘 5 補 03 03 03;... 若除 8 整除,則補 08 08 08 08 08 08 08 08。
還原時,讀取最後區塊的最後 Bytes,若為 01 就取前 7 Bytes、02 取前 6 Bytes、03 取前 5 Bytes... 若為 08 則整個區塊丟棄,原始資料到前一區塊為止。
就醬,靠著長度整除 8 硬補一組 8 個 8,雖然浪費 8 個 Bytes,原本無法辨別最後區塊是填補後結果還是原始資料的困擾,就這麼巧妙解決了,聰明。不過,這個做法也有限制:其適用區塊長度只到 255,且區塊愈大,長度整除時浪費的空間/頻寬就愈多。儘管如此,PKCS #5/#7 在一般應用仍是簡單有效的填充方法。
最後,用一小段 C# 實測結束這回合。
for (int i = 1; i < 10; i++)
{
var data = new byte[i];
for (int j = 0; j < i; j++) data[j] = (byte)0xff;
var padded = pad(data, 8);
var trimmed = trimPadding(padded);
Console.WriteLine(new string('-', 40));
Console.WriteLine($"OrigData: {BitConverter.ToString(data)}");
Console.WriteLine($" Padded: {BitConverter.ToString(padded)}");
Console.WriteLine($"Restored: {BitConverter.ToString(trimmed)}");
}
byte[] pad(byte[] data, int blockSize)
{
var padSize = blockSize - (data.Length % blockSize);
var padding = new byte[padSize];
for (var i = 0; i < padSize; i++)
{
padding[i] = (byte)padSize;
}
byte[] padded = new byte[data.Length + padSize];
data.CopyTo(padded, 0);
padding.CopyTo(padded, data.Length);
return padded;
}
byte[] trimPadding(byte[] data)
{
int padSize = data[data.Length - 1];
byte[] trimmed = new byte[data.Length - padSize];
Array.Copy(data, trimmed, trimmed.Length);
return trimmed;
}
Introduction to PKCS#5 padding.
Comments
# by 南無阿彌陀佛
辦別原始資料長度 辨別原始資料長度
# by 南無阿彌陀佛
byte[] pad(byte[] data, int blockSize) { var padSize = blockSize - (data.Length % blockSize); var padded = new byte[data.length + padSize]; for (var i = 0; i < padSize; i++) { padded[data.length + i] = (byte)padSize; } data.CopyTo(padded, 0); return padded; }
# by Jeffrey
to 南無阿彌陀佛,謝。