RAR3如何產生Key、IV，以及遇到的困難(1)
困難(1)的解法(慢)
困難(1)的解法(快)
遇到的困難(2)：密碼字數超過28個字
困難(1)和困難(2)的解法
RAR3如何產生Key、IV，以及遇到的困難(1)
材料：
[string]$password (使用者輸入)
[byte[]]$salt (位於RAR檔頭)
$seed = [System.Text.Encoding]::Unicode.GetBytes($password) + $salt
[byte[]]$iv = New-Object byte[] 16
$sha1 = [System.Security.Cryptography.SHA1]::Create()
$n = 0
for($i = 0; $i -lt 16; $i++){
for($j = 0; $j -lt 0x4000; $j++){
$n4bytes = [System.BitConverter]::GetBytes($n++)
# 每次會傳送 $seed 和 $n4bytes 進行處理
# 總共會傳送 (16 * 0x4000) 次
$sha1.TransformBlock($seed, 0, $seed.Length, $null, 0) > $null
# 只傳送 $n4bytes 的前 3 bytes
$sha1.TransformBlock($n4bytes, 0, 3, $null, 0) > $null
if ($j -eq 0){
# 計算 Hash
$sha1.TransformFinalBlock($seed, 0, 0) > $null
# 得到 IV 的一部份
$iv[$i] = $sha1.Hash[19]
# 遇到的困難(1)：
# 算出Hash之後，必須以 「還沒 TransformFinalBlock 的狀態」
# 繼續 TransformBlock
# 然而，現在已經 TransformFinalBlock 了，無法改變
}
}
}
# 計算 Hash
$sha1.TransformFinalBlock($seed, 0, 0) > $null
$hash = $sha1.Hash
# 得到 Key
[byte[]]$key = $hash[3..0] + $hash[7..4] + $hash[11..8] + $hash[15..12]
困難(1)的解法(慢)
$seed = [System.Text.Encoding]::Unicode.GetBytes($password) + $salt
[byte[]]$iv = New-Object byte[] 16
$sha1 = [System.Security.Cryptography.SHA1]::Create()
for($i = 0; $i -lt 16; $i++){
# 算1次，得到$iv[0]
# 算 1*0x4000 + 1 次，得到 $iv[1]
# 算 15*0x4000 + 1 次，得到 $iv[15]
$n = 0
for($j = 0; $j -lt $i*0x4000 + 1; $j++){
$n4bytes = [System.BitConverter]::GetBytes($n++)
$sha1.TransformBlock($seed, 0, $seed.Length, $null, 0) > $null
$sha1.TransformBlock($n4bytes, 0, 3, $null, 0) > $null
}
$sha1.TransformFinalBlock($seed, 0, 0) > $null
$iv[$i] = $sha1.Hash[19]
$sha1.Initialize()
}
# 算 16*0x4000 次，得到 $key
$n = 0
for ($i = 0; $i -lt 16*0x4000; $i++){
$n4bytes = [System.BitConverter]::GetBytes($n++)
$sha1.TransformBlock($seed, 0, $seed.Length, $null, 0) > $null
$sha1.TransformBlock($n4bytes, 0, 3, $null, 0) > $null
}
# 計算 Hash
$sha1.TransformFinalBlock($seed, 0, 0) > $null
$hash = $sha1.Hash
# 得到 Key
[byte[]]$key = $hash[3..0] + $hash[7..4] + $hash[11..8] + $hash[15..12]
困難(1)的解法(快)
$seed = [System.Text.Encoding]::Unicode.GetBytes($password) + $salt
[byte[]]$iv = New-Object byte[] 16
# 只有SHA1Managed可以
$sha1 = [System.Security.Cryptography.SHA1Managed]::new()
$sha1Type = $sha1.gettype()
$Field_count = $sha1Type.GetField('_count', 36)
$Field_stateSHA1 = $sha1Type.GetField('_stateSHA1', 36)
$Field_buffer = $sha1Type.GetField('_buffer', 36)
[Int64]$_count_copy = 0
[UInt32[]]$_stateSHA1_copy = New-Object UInt32[] 5
[byte[]]$_buffer_copy = New-Object byte[] 64
$n = 0
for($i = 0; $i -lt 16; $i++){
for($j = 0; $j -lt 0x4000; $j++){
$n4bytes = [System.BitConverter]::GetBytes($n++)
$sha1.TransformBlock($seed, 0, $seed.length, $null, 0) > $null
$sha1.TransformBlock($n4bytes, 0, 3, $null, 0) > $null
if ($j -eq 0){
# 取得 $sha1 狀態
$_count = $Field_count.GetValue($sha1)
$_stateSHA1 = $Field_stateSHA1.GetValue($sha1)
$_buffer = $Field_buffer.GetValue($sha1)
# 備份 $sha1 狀態
$_count_copy = $_count
[array]::Copy($_stateSHA1, $_stateSHA1_copy, 5)
[array]::Copy($_buffer, $_buffer_copy, 64)
# 計算Hash
$sha1.TransformFinalBlock($seed, 0, 0) > $null
$iv[$i] = $sha1.Hash[19]
# 還原 $sha1 狀態
$sha1.Initialize()
$Field_count.setValue($sha1, $_count_copy)
[array]::Copy($_stateSHA1_copy, $_stateSHA1, 5)
[array]::Copy($_buffer_copy, $_buffer, 64)
}
}
}
$sha1.TransformFinalBlock($seed, 0, 0) > $null
$hash = $sha1.Hash
[byte[]]$key = $hash[3..0] + $hash[7..4] + $hash[11..8] + $hash[15..12]
遇到的困難(2)：密碼字數超過28個字
# 當密碼字數超過28個字，會使$seed長度大於64
$seed = [System.Text.Encoding]::Unicode.GetBytes($password) + $salt
$sha1.TransformBlock($seed, 0, $seed.length, $null, 0) > $null
<#
$sha1 在TransformBlock的時候，每次處理 64 bytes的資料
剩下來不足 64 bytes 的資料，會放到 buffer 暫時存放
當$seed送去TransformBlock時
會把部份資料複製到buffer、湊足 64 bytes以進行處理
然後，再從 $seed的某起點、讀取64bytes進行處理
RAR3 SHA1特別之處：
從$seed某起點、讀取 64bytes 進行處理之後，
從$seed某起點、寫入 64bytes 到$seed
造成$seed內容的改變
當$seed長度66：
當buffer資料長度為0：
從$seed起點0、讀取 64bytes 進行處理，不寫入資料到$seed
剩餘 2bytes 存入buffer
當buffer資料長度為62：
從$seed起點0、讀取 2 bytes、湊足 64 bytes以進行處理
從$seed起點2、讀取 64bytes 進行處理
從$seed起點2、寫入 64bytes 到$seed
當$seed長度130：
當buffer資料長度為0：
從$seed起點0、讀取 64bytes 進行處理，不寫入資料到$seed
從$seed起點64、讀取 64bytes 進行處理
從$seed起點64、寫入 64bytes 到$seed
剩餘 2bytes 存入buffer
當buffer資料長度為62：
從$seed起點0、讀取 2 bytes、湊足 64 bytes以進行處理
從$seed起點2、讀取 64bytes 進行處理
從$seed起點2、寫入 64bytes 到$seed
從$seed起點66、讀取 64bytes 進行處理
從$seed起點66、寫入 64bytes 到$seed
#>
困難(1)和困難(2)的解法
使用RAR3_SHA1.cs
PS R:\> Add-Type -Path .\RAR3_SHA1.cs
PS R:\> $sha1 = new-object SHA1SP.SHA1SP
PS R:\>
PS R:\> [byte[]]$data = 11, 12, 13
PS R:\> $sha1.update($data)
PS R:\> $r = $sha1.digest()
PS R:\> [System.BitConverter]::ToString($r)
0D-52-37-C1-4C-75-22-CD-24-6A-D7-67-38-26-25-6F-A5-62-0A-80
PS R:\>
PS R:\> [byte[]]$data2 = 21, 22, 23
PS R:\> $sha1.update($data2)
PS R:\> $r = $sha1.digest()
PS R:\> [System.BitConverter]::ToString($r)
60-92-DE-71-DB-96-D8-F9-C6-BC-57-14-BB-D9-FA-54-D3-42-7F-A4
PS R:\>
PS R:\> $sha1.Reset()
PS R:\> $sha1.update($data + $data2)
PS R:\> $r = $sha1.digest()
PS R:\> [System.BitConverter]::ToString($r)
60-92-DE-71-DB-96-D8-F9-C6-BC-57-14-BB-D9-FA-54-D3-42-7F-A4
PS R:\>
ps1新增程式碼
Add-Type -Path .\RAR3_SHA1.cs
$sha1 = new-object SHA1SP.SHA1SP
// 當密碼超過28字時，可能會寫資料回來
// 要用New-Object另外準備空間，不能使用原本的$seed
$seedNew = New-Object byte[] $seed.length
[array]::Copy($seed, 0, $seedNew, 0, $seed.length)
ps1修改程式碼
$sha1.update($seedNew)
$sha1.update($n4bytes[0..2])
$hash = $sha1.digest()
// RAR3_SHA1.cs
// https://zh.wikipedia.org/wiki/SHA-1
// https://github.com/mono/mono/blob/master/mcs/class/corlib/System.Security.Cryptography/SHA1CryptoServiceProvider.cs
// For caculating RAR 3 key IV
// It's different than other SHA1 algorithm when input data length greater than 64
namespace SHA1SP {
public class SHA1SP {
private uint[] h = new uint[5];
private uint[] w = new uint[80];
private byte[] buffer = new byte[64];
private long count = 0;
public SHA1SP (){
h[0] = 0x67452301;
h[1] = 0xEFCDAB89;
h[2] = 0x98BADCFE;
h[3] = 0x10325476;
h[4] = 0xC3D2E1F0;
}
public void Reset (){
h[0] = 0x67452301;
h[1] = 0xEFCDAB89;
h[2] = 0x98BADCFE;
h[3] = 0x10325476;
h[4] = 0xC3D2E1F0;
count = 0;
}
public void update(byte[] data){
if (null == data){return;}
// 取得buffer資料長度
int bufferCount = (int)count & 0x3f;
long start = 0;
long Len = data.Length;
long end = start + Len;
// 更新：已輸入了多少資料
count += Len;
bool afterFirstBlock = false;
// 當buffer有資料
if (bufferCount != 0){
// n = buffer剩餘空間
int n = 64 - bufferCount;
if (Len < n){// buffer剩餘空間足夠、可以放全部資料
System.Array.Copy(data, 0, buffer, bufferCount, Len);
return;
}else{// 把buffer剩餘空間全部用掉、用來放一部份資料
System.Array.Copy(data, 0, buffer, bufferCount, n);
process64(buffer, 0);
start += n;
afterFirstBlock = true;
}
}
while (start + 64 <= end) {
process64(data, start);
if (afterFirstBlock){// RAR3 SHA1 特別的部份：會寫資料回data
for (int i=0, j=64; j < 80; i+=4, j++){
data[start + i] = (byte)(w[j]);
data[start + i + 1] = (byte)(w[j] >> 8);
data[start + i + 2] = (byte)(w[j] >> 16);
data[start + i + 3] = (byte)(w[j] >> 24);
}
}
start += 64;
afterFirstBlock = true;
}
if (start < end){// 未處理的資料，存到buffer
System.Array.Copy(data, start, buffer, 0, end - start);
}
return;
}
public byte[] digest(){
if (count == 0){return null;}
// 取得buffer資料長度
int bufferCount = (int)count & 0x3f;
int finalBlockLen = 64;
// 如果「buffer資料長度」+「至少 1 byte 補 0」+ 「8 bytes 長度資訊」大於 64
if (bufferCount + 1 + 8 > 64){finalBlockLen = 128;}
byte[] finalBlock = new byte [finalBlockLen];
int i = 0;
// 複製 buffer資料 到 finalBlock
for (; i < bufferCount; i++){
finalBlock[i] = buffer[i];
}
// 至少 1 byte 補 0
// 靠近buffer資料的那 1 bit 為 1
// 1000 0000
finalBlock[i++] = 0x80;
// 計算補 0 要補到哪個位置才停止
int zeroEnd = finalBlockLen - 8;
// 補 0
for (; i < zeroEnd; i++){
finalBlock[i] = 0;
}
// 計算資料長度為多少 bits
ulong TotalCount = (ulong)(count * 8);
finalBlock[i++] = (byte)(TotalCount >> 56);
finalBlock[i++] = (byte)(TotalCount >> 48);
finalBlock[i++] = (byte)(TotalCount >> 40);
finalBlock[i++] = (byte)(TotalCount >> 32);
finalBlock[i++] = (byte)(TotalCount >> 24);
finalBlock[i++] = (byte)(TotalCount >> 16);
finalBlock[i++] = (byte)(TotalCount >> 8);
finalBlock[i] = (byte)(TotalCount);
// 備份狀態
uint[] hCopy = new uint[5];
for (i = 0; i < 5; i++){
hCopy[i] = h[i];
}
process64(finalBlock, 0);
if (finalBlockLen == 128){
process64(finalBlock, 64);
}
byte[] result = new byte[20];
// 得到 Hash
for (i = 0; i < 5; i++){
result[i*4] = (byte)(h[i] >> 24);
result[i*4+1] = (byte)(h[i] >> 16);
result[i*4+2] = (byte)(h[i] >> 8);
result[i*4+3] = (byte)(h[i]);
}
// 還原狀態
for (i = 0; i < 5; i++){
h[i] = hCopy[i];
}
return result;
}
private void process64(byte[] data, long start){
int i;
long j;
// 把 64 bytes 資料轉成 16個 uint
for(i = 0; i < 16; i++){
j = start + i*4;
w[i] = (uint)(data[j] << 24 | data[j+1] << 16 | data[j+2] << 8 | data[j+3]);
}
// 用 16個 uint 產生 64個 uint
// 結果，總共有 80個 uint
uint temp;
for(i = 16; i < 80; i++){
temp = w[i-3] ^ w[i-8] ^ w[i-14] ^ w[i-16];
w[i] = (temp << 1) | (temp >> 31);
}
// 複製一份資料，以供運算
uint a = h[0];
uint b = h[1];
uint c = h[2];
uint d = h[3];
uint e = h[4];
uint f = 0;
uint k = 0;
for(i = 0; i < 80; i++){
if (i < 20){
f = (b & c) | ((~ b) & d);
k = 0x5A827999;
}else if (i < 40){
f = b ^ c ^ d;
k = 0x6ED9EBA1;
}else if (i < 60){
f = (b & c) | (b & d) | (c & d);
k = 0x8F1BBCDC;
}else{
f = b ^ c ^ d;
k = 0xCA62C1D6;
}
temp = (a << 5 | a >> 27) + f + e + k + w[i];
e = d;
d = c;
c = (b << 30) | (b >> 2);
b = a;
a = temp;
}
// 更新SHA1狀態。可能會溢位
h[0] += a;
h[1] += b;
h[2] += c;
h[3] += d;
h[4] += e;
return;
}
}
}
沒有留言:
張貼留言