1990年R. Merkle認識到DES快結束其生命期並提出了二個密碼系統作為可能的替代品,當時其基本設計原則如下:

1.DES的56位鑰長太小。考慮到增長密鑰的代價是微不足道的(計算機存儲器既廉又豐),應該增長密鑰。

2．DES中廣泛使用置換操作,雖適合於硬件實現,但軟件實現是很困難的。DES的快速軟件實現顺利获得查表法實現置換,查表法可给予與置換同樣的“擴散”特性並更為靈活。

3.DES中S盒太小每個盒只有64個4位項。既然存儲器更大了,S盒也應加大,而且應同時使用8個S盒。雖然這適合於硬件實現,但對軟件似乎是個不合理的限制,應該使用更大並且是順序的(而不是並行的)S盒。

4.DES中的初始和最後置換普遍認為在密碼效果上沒有意義,應取消。所有DES的快速實現都預計算每輪中的密鑰,因此沒有理由不把該計算設計成更為複雜。

5.不像DES,S盒的設計應該公開。

Khufu是64位的塊密碼算法,64位明文塊第一时间分成各為32位的左右二半L和R,L和R，都與同一子鑰異或,再經過類似於DES的幾輪疊代。每一輪中,L的最低字節用作256項S盒的輸入,S盒中每一項為32位。S盒中選取的32位項與R異或,接着L循環移位8的倍數位,L與R交換,一輪結東。S盒本身也不是靜止的,每8輪改變一次。最後一輪之後,L和R與更多的子鑰異或,並且合併在一起形成密文塊。

雖然密鑰的某些部分在算法開始和結尾處與加密塊異或,密鑰的主要目的是生成S盒,這些S盒是保密的且本質上是部分密鑰。 Merkle的算法需要512位(64位元組)鑰長,並由一個算法從密鑰生成S盒。算法的輪數還未公開, Merkle推測幾乎所有應用場合都採用16,24或32輪(他把輪數限制為8的倍數)。

由於 Khufu密鑰相關且有保密的S盒,差分分析對它毫無結果。如果蠻力攻擊是攻擊Khufu的最好方法,它是非常難以攻破的:任何情況下,22的複雜度是不可想像的。

Khafre是由 Merkle提出的二個密碼系統中的另一個( Khufu和 Khafre是以二位埃及法老而取名的), Khafre的設計類似於 Khufu,只是 Khafre是為沒有預計算時間的應用場合而設計的。S盒獨立於密鑰, Khafre採用一組標準的S盒,並且密鑰與加密塊異或不僅在首輪之前和末輪之後,而且每8輪之後都執行一次。

Merkle推測 Khafre中鑰長為64或128位,並且 Khafre的加密輪數比 Khufu多,再加上Khafre的每輪都比 Khufu更複雜,使得 Khafre要比 Khufu慢。另一方面, Khafre沒有預計算,所以加密少量數據要比 Khufu快一些。

1990年, Biham和 Shamir用差分密碼分析技術攻擊 Khafre,他們以約1500個選擇明文攻破16輪的 Khafre,用PC機運行了約1個小時。