手动解密微软Agile Encryption的ECMA-376文档

先给一些参考资料,如果有漏掉的部分,可以参考这里:

  1. [MS-OFFCRYPTO]: Office Document Cryptography Structure
  2. [MS-CFB]: Compound File Binary File Format
  3. Standard ECMA-376 Office Open XML File Formats
  4. Apache POI Encryption Support

一 解析CFB文件结构

先介绍一下CFB文件结构,以从中取出解密需要的信息:

  1. CFB文件被切分为等长的Sector,然后用如下方式组织起来:
    Header Sector + Sector #0 + Sector #1 + …
    由于有Header的存在,算Sector偏移的时候,Sector Number需要加一。
  2. Sector之间由FAT表关联,形成多条Sector链
    FAT[0] – Sector #0 的下一个Sector Number (4 bytes)
    FAT[1] – Sector #1 的下一个Sector Number

    还有一些特殊的内容,比如:
    FAT Sector (0xFFFFFFFD)
    链结尾 (0xFFFFFFFE)
    空的占位符 (0xFFFFFFFF)

    例子:
    FAT[0]: fd ff ff ff
    FAT[1]: 04 00 00 00

  3. FAT表也存储在Sector里,FAT表由DIFAT表关联,关联方式和FAT一致,唯一的区别是前109个DIFAT项,被直接存储在Header Sector里。

    例子:
    DIFAT[0]: 00 00 00 00
    DIFAT[1]: 07 00 00 00

  4. Sector内存储了各种类型的数据,包括一个简单的类似文件系统的树状结构。

    其中,Storage类似于文件夹,Stream类似于文件。
    Root Storage是唯一的根目录,下面挂其他的Storage或者Stream。

    由于Stream大小比较大,还提供了Mini Stream,用于存储比较小的数据。

  5. Header的结构参考[MS-CFB] 2.2 Compound File Header,一些关键信息如下:
    1. Byte Order – 确定字节序 (0xFFFE)
    2. Sector Shift – 单个Sector的大小 0x9 (512B) 或者 0xc (4096B)
    3. Mini Sector Shift – 单个Mini Sector的大小 0x6 (64B)
    4. Mini Stream Cutoff Size – 小于这个大小的数据,被放在Mini Stream里 (4096B)
    5. First Directory Sector Location – Directory Stream的起始Sector Number
    6. First Mini FAT Sector Location – Mini FAT表的起始Sector Number
    7. First DIFAT Sector – DIFAT表的起始Sector Number (如果Header里的109项已经够用了,则为链结尾 – 0xFFFFFFFE)
  6. 接下来解析Directory Stream所在的起始Sector
    1. 偏移:[(Sector Number + 1) * Sector Shift]
    2. 每个Directory Entry的大小是128B,如果Sector大小为512B,则每个Sector可以放四个Directory Entry
    3. Directory Entry的结构参考[MS-CFB] 2.6.1 Compound File Directory Entry,一些关键信息解释如下:
      1. Directory Entry Name – 项名称 一般第一个为Root Entry [UTF-16]
      2. Object Type – 0x0 未分配 0x1 Storage 0x2 Stream 0x5 Root Storage
      3. Child ID:子项Directory Entry的ID (如果没有子项,则为0xFFFFFFFF)
      4. Left Sibling ID: 左兄弟项Directory Entry的ID (如果没有左兄弟项,则为0xFFFFFFFF)
      5. Right Sibling ID: 右兄弟项Directory Entry的ID (如果没有右兄弟项,则为0xFFFFFFFF)
      6. Starting Sector Location – 对Stream而言,表示起始Sector Number;对Root Storage而言,则指示了Mini Stream的起始Sector Number
      7. Stream Size: 对Stream而言,表示数据大小;对Root Storage而言,则表示Mini Stream的大小
    4. 例子
      Directory Entry [0]:
      Directory Entry Name: 52 00 6f 00 6f 00 74 00 20 00 45 00 6e 00 74 00 72 00 79 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 [UTF-16]
      Directory Entry Name: Root Entry [UTF-16]
      Directory Entry Name Length: 16 00
      Object Type: 05
      Color Flag: 00 [0x00 Red 0x01 Black]
      Left Sibling ID: ff ff ff ff
      Right Sibling ID: ff ff ff ff
      Child ID: 0a 00 00 00
      CLSID: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
      State Bits: 00 00 00 00
      Creation Time: 00 00 00 00 00 00 00 00
      Modified Time: 00 3d 2a 3d 8e 12 d2 01
      Starting Sector Location: 03 00 00 00
      Stream Size: 00 08 00 00 00 00 00 00
  7. 根据以上的内容,我们可以得到两个关键的Stream
    1. EncryptionInfo Stream,这个Stream包含一个明文的XML字符串,包含我们需要的解密相关信息
      1. 从提供的密码 和 EncryptedKeyValue里解密中间密钥 encryption/keyEncryptors/keyEncryptor/encryptedKey
        1. spinCount – 加密多少轮,例如10000
        2. saltSize
        3. blockSize
        4. keyBits – 决定AES128 或者 AES256
        5. hashSize
        6. cipherAlgorithm – 例如AES
        7. cipherChaining – 例如CBC
        8. hashAlgorithm – 例如SHA512
        9. saltValue – 用于加密中间密钥的盐值 (base64 编码)
        10. encryptedKeyValue – 加密后的中间密钥 (base64 编码)
      2. 用上面获得的中间密钥解密实际数据 encryption/keyData
        1. saltSize
        2. blockSize
        3. keyBits
        4. hashSize
        5. cipherAlgorithm
        6. cipherChaining
        7. hashAlgorithm
        8. saltValue
    2. EncryptedPackage Stream,这个Stream包含我们待解密的数据
      1. Stream Size : 8 bytes (无符号整数)
      2. Encrypted Data: variable size

二 解密中间密钥

我们用AES256 + SHA512的组合举例, AES256需要Key和初始向量IV

  1. 预先处理
    1. Salt Value 和 Encrypted Key Value 在XML里是base64编码的,我们需要先解码为二进制 base64.b64decode()
    2. 用户输入的密码也需要用utf-16小尾编码 “password”.encode(“utf-16le”)
  2. 获得Key
    1. SHA512编码 (encryptedKey/saltValue + 用户输入的密码)
      pwHash = hashlib.sha512()
      pwHash.update(saltValue)
      pwHash.update(password)
      key = pwHash.digest()
    2. SHA512编码spinCount轮 Hn = H(count + Hn-1)
      其中count为从0开始的无符号32位数
      for i in xrange(spinCount):
      pwHash = hashlib.sha512()
      pwHash.update(struct.pack(“<I”, i))
      pwHash.update(key)
      key = pwHash.digest()
    3. SHA512编码 Hfinal = H(Hn + BlockKey)
      如果Hfinal大于keyBits,则需要按keyBits截断;
      反之,如果小于,则需要用0x36来append补足
      pwHash = hashlib.sha512()
      pwHash.update(key)
      pwHash.update(struct.pack(‘<BBBBBBBB’, 0x14, 0x6e, 0x0b, 0xe7, 0xab, 0xac, 0xd0, 0xd6))
      key = pwHash.digest()[:32]
  3. 获得IV
    1. 就是encryptedKey/saltValue
    2. 如果大于blockSize,则按blockSize截断
    3. 反之,如果小于,则需要用0x36来append补足
  4. 解密encryptedKey/encryptedKeyValue得到中间密钥
    aes = AES.new(key, AES.MODE_CBC, iv)
    secretKey = aes.decrypt(encryptedKeyValue)

三 解密EncryptedPackage Stream

解密的时候,每4096B为一个解密单元,count从0开始的32位无符号整数。

  1. 获得IV H = H(keyData/saltValue + count)
    contentHash = hashlib.sha512()
    contentHash.update(saltValue)
    contentHash.update(struct.pack(“<I”, count))
    iv = contentHash.digest()
  2. 解密当前单元
    aes = AES.new(secretKey, AES.MODE_CBC, iv)
    content = aes.decrypt(encryptedContent)

 

解决Firefox Crashes

Firefox最近老Crash,试过安全模式,没问题,但再试禁用所有addons ( plugins / extensions / default appearance ) 和 禁用硬件加速,依然会crash,看了一下。

  1. about:support
    • 查看Crash Report,可以看到Crash到d3dcompiler_47.dll里面
  2. about:config
    • 禁用WebGL,webgl.disabled=true
  3. 其他有用的about page,全部列在about:about

The adventure of my iPhone 3G

常在河边走,哪有不湿鞋… 好吧…我一打梦觉,就湿了…不过,故事还是得从头说起…

我是一个版本控,对于版本有着近乎强迫症的冲动。
我知道这不理智:更新太快,自己当小白鼠或者垫脚石;更新太频繁,白费很多毫无意义的人力和时间。
但人不总是那么理性的思考问题。特别当这个问题,其实并不是那么的重大的时候…

奇特的是,我对于手机操作系统和软件的版本,却有着出奇的耐受力。iPhone从买来到现在,就为了“复制粘贴”功能,刷了一次iOS3.x,之后就再也没动过了。
至于理由,主要原因当然还是因为我的iPhone是有锁版的水货,升级不是那么方便。但也可能和下面这篇很有名的文章有些许联系。

<Can We Make Operating Systems Reliable and Secure?>
by Andrew S. Tanenbaum, Jorrit N. Herder, and Herbert Bos

When was the last time your TV set crashed or implored you to download some emergency software update from the Web? After all, unless it is an ancient set, it is just a computer with a CPU, a big monitor, some analog electronics for decoding radio signals, a couple of peculiar I/O devices (e.g., remote control, built in VCR or DVD drive) and a boatload of software in ROM.

This rhetorical question points out a nasty little secret that we in the computer industry do not like to discuss: why are TV sets, DVD recorders, MP3 players, cell phones, and other software-laden electronic devices reliable and secure and computers not?

这是很值得思考的一个问题,但还是不要把话题扯远了,拉回来说我的iPhone 3G历险记。

最近,越来越多的App Store程序开始鄙视iOS 3.x的系统,我终于开始觉得忍无可忍,决定花点时间来刷机,升级为iOS 4.x的系统。

下面是必备的两个网址,可以说是列举的太清楚了:

我先大概说一下这些乱七八糟的东西是什么意思。

在iPhone里,设置->通用->关于本机 下面可以看到:

  • 版本 就是你的iPhone操作系统iOS的版本。这也是我升级的目标,从3.x升级为4.x。新增的内容,可以从上面提到的第一个链接里看到。
    你基本可以理解为把Windows XP SP2 升级为 Windows XP SP3。
  • 型号 是你机器的模型号。我的是MB046LL。稍微Google一下,就知道我这机器是美版有锁的。
    所谓有锁,就是说这机器因为合约的问题,只能使用美国AT&T公司的网络(通常这意味着手机更便宜),其他的SIM卡插上去无法激活,用不了。
    所以我这种机器,需要Unlock解锁 ,才能使用我中国移动的SIM卡。(另外一种办法是使用卡贴,就是在SIM卡上加一层东西,让iPhone误以为是AT&T的SIM卡)
    而Unlock需要用到的软件,叫做UltraSnow超雪。
    iPhone上的程序出于安全性和稳定性等等因素的考虑,是在一个个沙盒中运行,与外界有着清晰定义的边界,同时,权限也受到极大的限制。
    因此像UltraSnow这种程序是不可能以正常的方式实现的,他需要更高的权限。
    要想获得更高的权限,以安装UltraSnow,我们需要先JailBreak越狱我们的iPhone,让我们逃出iPhone沙盒的监牢,自由驰骋。
  • 调制解调器固件 就是我们通常说的Baseband基带版本号。 这也是刷机最容易出问题的地方。
    原因在于,刷机刷坏了,我们可以简单的重新刷一遍覆盖回去。但基带版本却只能升高,不能降低。
    前面提到过UltraSnow解锁,其实就是需要在基带中找到他的漏洞以破除限制。
    我们有iPhone Dev Team等一些组织在进行解锁和越狱的工作,但这毕竟需要时间。
    在破解出来以前,如果你提前升级刷新iOS, 导致基带升级,就会让你的iPhone能够越狱,却无法解锁,从而变身为iPod Touch。

在刷机之前,必须先确认好上面这些信息。从上面提供的两个链接,可以查到所有你需要的版本信息。

对于我的iPhone 3G而言,最新的iOS版本是4.2.1,也是我升级的目标版本号。值得一提的是,这个版本号是Final的,也就是说对iPhone 3G而言,以后这个版本号不会再增加了。

4.2.1对应的Baseband号是05.15.04, 我如果刷官方的固件(也就是来自苹果的iOS4.2.1映像),就会把我的iPhone的基带升级到05.15.04。虽然4.2.1可以越狱,但05.15.04这个基带版本是UltraSnow不能解锁的。

所以正确的做法是保留当前的基带升级。这种方式需要自己制作iOS4.2.1的固件,而不是使用官方的固件。制作方法在Mac上用PwnTools,在Windows上用SnowBreeze。制作好之后,在最新版的iTunes里用Shift+Update进行升级就可以了。这样就可以即升级了系统,又保留了基带,还越了狱。

到目前为止,都还正常。问题开始于我对基带版本的追求。

我之前刷iOS3.x的时候的基带版本是04.26.08。虽然05.15.04是没破解的,但05.13.04是有破解的,所以我想先刷到对应的iOS4.0.2,以升级基带到有破解的05.13.04,然后再保留基带升级iOS到4.2.1。

想来一切顺利,但可恶的苹果在iTunes里恢复固件的时候设了一个障碍,就是网上看到的那个SHSH Blob。这个东西是用来阻止你升级到较老的iOS版本的。也就是说,我用iTunes升级4.2.1没问题,但升级到4.0.2就必须得有那个SHSH Blob,也就是苹果的“YES, GO AHEAD”的响应。要绕过这个,你得首先之前备份过4.0.2针对你设备的SHSH Blob。这既可以自己用工具备份,也可以用Cydia来备份。如果用Cydia备份过,就可以改hosts文件来指向Cydia提供的一个伪造的应答服务器,欺骗iTunes让你升级到较老的iOS版本。

简言之,对我而言,就算失败了。于是,我一怒之下,直接升级到了4.2.1,当然固件也就升到了没有破解的05.15.04。这纯粹是冲动的惩罚… 于是iPhone也摇身一变,成了iPod Touch。

由于4.2.1是Final的iOS,我也不指望以后再升级这个手机。更关键的是,有更多更新的设备让iPhone Dev Team等去忙,要干等iPhone 3G 05.15.04的解锁是不现实的。

我最后的期望就是继续升级到iPad baseband 06.15.00。这个基带是有UltraSnow破解的,但坏处是:

1. GPS废了;
2. 以后不能再回退到iPhone的官方固件或基带;
3. 据说有耗电量大,发热等情况。

升级过程也不是很顺畅,因为RedSn0w的“install ipad baseband”在我的几台电脑上都要异常退出,我最后是在一台Mac OS X Snow Leopard的虚拟机里,用PwnTool做了个自制固件来升级基带到iPad的06.15.00。不过如前所述,PwnTool制作自制固件一般都是为了保留基带不升级。所以你得下载专门的一个Unlock版。

之后就很自然的装UltraSnow解锁基带, 除了GPS都正常了。耗电量和发热的问题也是可以解决的。只需要用RedSnow来Deactive你的iPhone,然后装SAM来从你的iPhone自身激活自己。

最后值得一提的,4.x系统里多任务的选项就不要开了,iPhone 3G那点内存,完全没法支持多任务的。尽管iOS 4.x的内存管理比3.x好太多太多 。

Google Code Jam 2011 (Qualification)

书接上篇

1. [84%/98%] Bob Trust: 两个机器人并行依次按钮

由于要依次按钮,所以并行能节省的时间,只有另外一个机器人移动的时间,而它按钮的那一秒钟是不能节省的。

2. [87%/82%] Magicka:依次合并或者清除元素

由于即使是大数据集,合并列表和冲突列表个数也不过36和28,所以最好直接把这两个列表反向来进行匹配,而不是在后面的匹配测试中去正反测试两遍。
另外注意先合并,后判冲突。

3. [90%/85%] Candy Splitting:加法改异或

按题目叙述,不难发现Patrick的错误加法真值表与异或XOR运算相同。由于没有进位,可以单独看每个二进制位。
如果某一个二进制位上,1的个数为奇数,则无论如何划分,都不可能使得最后异或结果相等。
如果1的个数为偶数,则可以任意划分,但需要保证可怜的Patrick至少分到一个糖果。
所以排序后取最小的数给Patrick,其他的全部留给Sean。

4. [58%/97%] GoroSort:概率排序

首先注意,下面这个Smallest的条件很容易被忽略掉:
The second line of each test case will contain a permutation of the N smallest positive integers.

然后由于每个数都已经知道最后需要所在的位置,所以排除掉已经在目标位置的情况,其他的每hit一次,有1/2的机会回到正常的位置,再加上,占据现有位置的那个数,以后会有1/2的机会回到它自己的位置,所以只需要每个不在目标位置的数上累计加一就能得出结果。

这题最挨打的,就是那个%.6lf。 我是用整数表示,然后后面加6个0。这个实在太误导了,让人以为会计算很复杂的概率。

PS 最后,这次的GCJ Command Line Tool还蛮好用的,呵呵~

GCJ 2011 Qualification Round Solution Download

汉字叔叔

很多事情,确实该中国人自己干,比如花20年把汉字字源信息化,却让老外给做了…

之前给这位Richard Sears发了一封信,称赞了一下他做的事情,建议他在捐助页面,加入支付宝的支持。信是英文的,今天收到的回信,居然是中文的,不愧是“汉字叔叔”,呵呵~

你好TIAN!

谢谢你对我的赞赏。
很抱歉这么久才回复你。 每天大量的问题需要解决, 资料的补充, 大量的EMAIL需要回复。
我刚刚获得一个支付宝的帐户和签约同支付宝公司, 我正在将支付宝的接口安装到我的网站, 很快就会完成, 这样就很方便那些愿意赞助我的中国朋友。
再次感谢!
春节快乐!

Richard

相关链接:http://www.chineseetymology.org/

Poem forwarded by Duo Liang Lin to his couple of friends

What do you really want from us?
By Anonymous

When we were the Sick Man of Asia, We were called The Yellow Peril.
When we are billed to be the next Superpower, we are called The Threat.
When we closed our doors, you smuggled drugs to open markets.
When we embrace Free Trade, You blame us for taking away your jobs.
When we were falling apart, You marched in your troops and wanted your fair share.
When we tried to put the broken pieces back together again, Free Tibet
you screamed, It Was an Invasion!
When tried Communism, you hated us for being Communist.
When we embrace Capitalism, you hate us for being Capitalist.
When we have a billion people, you said we were destroying the planet.
When we tried limiting our numbers, you said we abused human rights.
When we were poor, you thought we were dogs.
When we loan you cash, you blame us for your national debts.
When we build our industries, you call us Polluters.
When we sell you goods, you blame us for global warming.
When we buy oil, you call it exploitation and genocide.
When you go to war for oil, you call it liberation.
When we were lost in chaos and rampage, you demanded rules of law.
When we uphold law and order against violence, you call it violating human rights.
When we were silent, you said you wanted us to have free speech.
When we are silent no more, you say we are brainwashed-xenophobics.
Why do you hate us so much, we asked.
No, you answered, we don’t hate you.
We don’t hate you either, But, do you understand us?
Of course we do, you said,We have AFP, CNN and BBC’s…
What do you really want from us?
Think hard first, then answer… Because you only get so many chances.
Enough is Enough, Enough Hypocrisy for This One World.
We want One World, One Dream, and Peace on Earth.
This Big Blue Earth is Big Enough for all of Us.

============= Interesting Response =============

Echoing the Voice of the Voiceless
By Ann Lau

When Empress Dowager paid indemnity to the eight nations, the U.S. used it for the first Chinese students to study abroad.
When Sun Yat Sen came to the U.S. as a fugitive, the U.S. opened her arms.
When China was invaded by Imperial Japan, the U.S. sent in the Flying Tigers.
When China put up the bamboo curtain, the Chinese risked the shark infected sea to escape to Hong Kong and then to the west.
When the Dalai Lama called Mao as his Big Brother, it was not enough; religion is the opium of the people.
With Communism, the Chinese suffered the greatest famine in the history of mankind.
Again, the west welcomed those refugees.
When China was facing economic collapse, it was those Chinese who left China who first went back to establish commerce.
When China needed investments, the IMF came to its aid.
With Capitalism, corruption went rampant and the Chinese floating migrants became second class citizens in their own cities.
With a billion people, China has great potential; why is their government afraid of them?
Tell me why blind legal expert Chen Guangcheng was sentenced to jail when he helped villagers to file class action against forced abortion and sterilization?
Tell me why Wu Lihong, a farmer who became an environmentalist, was sentenced to jail when he tried to save Lake Tai?
Tell me why farmer Jiang Jinzhu called on outside China to help when his land and mushroom farm was illegally torn down?
Tell me why Hu Jia was sentenced to three and half years in jail when he wrote an article on the internet?
Tell me why attorney Teng Biao was kidnapped when he tried to help Hu Jia?
Tell me why Baixing’s editor-in-chief, Huang Liangtian was fired when he reported too many stories on corruption and official land grabs?
Tell me why Zeng Jinyan is in house arrest with her baby when she only blogged on the environment and AIDS?
Tell me why the petitioners in Beijing crowd around the western press and beg them to listen to their stories?
With their own fellow citizens unjustly treated, where is the outrage?
Tell me what top Chinese intellectuals said in their open letter on the Olympics and why they send their letter to the west?
Tell me what top Chinese intellectuals said in their open letter on the Tibet issue and why they send their letter to the west?
Why do Chinese in China call on the west to highlight their injustice?
Why do Chinese in China want the western press to report on their grievances?
Why do Chinese in China even went in front of the U.S. embassy to bring attention to their plights?
Could it be that their own government is not listening?
The west can turn a blind eye and close their ears to those Chinese people who pleaded for their help just as their own government have done.
There is little the west can do except to merely echo the voice of the voiceless.
If we even refuse to do that, then what kind of people are we?

Merry Christmas

愿所有的朋友,在新的一年中,依然能够找到心中那一份宁静,那一片净土~

送上一首我最喜爱的圣诞歌曲 – Silent Night by Billy Gilman,聊表心意… 圣诞快乐!

Silent Night

[歌词]

Silent night, holy night
All is calm, all is bright
Round yon virgin mother and child
Holy infant so tender and mild
Sleep in heavenly peace
Sleep in heavenly peace
Silent night, holy night
Son of God, love’s pure light
Radiant beams from thy holy face
With the dawn of redeeming grace
Christ, the Savior is born
Christ, the Savior is born
Christ, the Savior is born