firefox缓存哈希密钥生成算法错误

问题描述 投票：7回答：7

[a bug in Firefox（即使在新的Beta和布雷区中也是如此）可防止某些文件的缓存，因为该算法会在其缓存哈希中创建密钥。 Here is a link to the source code of the function。

我想确保可以缓存我网站的所有文件。但是，我不明白为什么他们的哈希函数无法为不同的URL创建唯一的键。我希望有人可以用伪代码或Java描述此mal函数。

在修复此错误之前，为开发人员创建一个实用程序以确保唯一的URL会很好。

EDIT：有一些非常有用的答案，但是，我需要更多逐步的帮助来创建一个实用程序来检查这些缓存混淆。获得一些可以重现firefox正在创建的键的Java代码将是很棒的。因此，开启了对这个问题的悬赏。

编辑2：这是部分工作的Java端口（使用processing编写）。注意底部的测试；前三个工作按预期进行，而其他三个则没有。我怀疑有关有符号/无符号整数的信息。建议？

//
// the bad collision function
// http://mxr.mozilla.org/mozilla/source/netwerk/cache/src/nsDiskCacheDevice.cpp#240
//

//248 PLDHashNumber
//249 nsDiskCache::Hash(const char * key)
//250 {
//251     PLDHashNumber h = 0;
//252     for (const PRUint8* s = (PRUint8*) key; *s != '\0'; ++s)
//253         h = PR_ROTATE_LEFT32(h, 4) ^ *s;
//254     return (h == 0 ? ULONG_MAX : h);
//255 }

//
//  a java port...
//

String getHash( String url )
{

//get the char array for the url string
char[] cs = getCharArray( url );

int h = 0;

//for (const PRUint8* s = (PRUint8*) key; *s != '\0'; ++s)
for ( int i=0; i < cs.length; i++ )
{  h = PR_ROTATE_LEFT32(h, 4) ^ cs[i];
}

//looks like the examples above return something in hex.
//if we get matching ints, that is ok by me.
//but for fun, lets try to hex the return vals?
String hexVal = hex( h );
return hexVal;
}

char[] getCharArray( String s )
{
  char[] cs = new char[s.length()];
  for (int i=0; i<s.length(); i++)
  { 
    char c = s.charAt(i);
    cs[i] = c;
  } 

  return cs;
}

//
// how to PR_ROTATE_LEFT32
//

//110 /*
//111 ** Macros for rotate left and right. The argument 'a' must be an unsigned
//112 ** 32-bit integer type such as PRUint32.
//113 **
//114 ** There is no rotate operation in the C Language, so the construct
//115 ** (a << 4) | (a >> 28) is frequently used instead. Most compilers convert
//116 ** this to a rotate instruction, but MSVC doesn't without a little help.
//117 ** To get MSVC to generate a rotate instruction, we have to use the _rotl
//118 ** or _rotr intrinsic and use a pragma to make it inline.
//119 **
//120 ** Note: MSVC in VS2005 will do an inline rotate instruction on the above
//121 ** construct.
//122 */
//...
//128 #define PR_ROTATE_LEFT32(a, bits) _rotl(a, bits)


//return an int (32 bit).  what do we do with the 'bits' parameter?  ignore?
int PR_ROTATE_LEFT32( int a, int bits )
{    return (a << 4) | (a >> (32-bits)); 
}

//
// examples of some colliding hashes
// https://bugzilla.mozilla.org/show_bug.cgi?id=290032#c5
//

//$ ./hashit "ABA/xxx.aba"
//8ffac222
//$ ./hashit "XyZ/xxx.xYz"
//8ffac222
//$ ./hashit "CSS/xxx.css"
//8ffac222
//$ ./hashit "JPG/xxx.jpg"
//8ffac222

//$ ./hashit modules_newsfeeds/MenuBar/MenuBar.css
//15c23729
//$ ./hashit modules_newsfeeds/ListBar/ListBar.css
//15c23729

//$ ./hashit modules_newsfeeds/MenuBar/MenuBar.js
//a15c23e5
//$ ./hashit modules_newsfeeds/ListBar/ListBar.js
//a15c23e5



//
// our attempt at porting this algorithm to java...
//

void setup( )
{

String a = "ABA/xxx.aba";
String b = "CSS/xxx.css";
String c = "CSS/xxx.css";
String d = "JPG/xxx.jpg";

println( getHash(a) ); //yes 8ffac222
println( getHash(b) ); //yes 8ffac222
println( getHash(c) ); //yes 8ffac222
println( getHash(d) ); //no [??] FFFFFF98, not 8ffac222

println( "-----" );

String e = "modules_newsfeeds/MenuBar/MenuBar.css";
String f = "modules_newsfeeds/ListBar/ListBar.css";

println( getHash(e) ); //no [??] FFFFFF8C, not 15c23729
println( getHash(f) ); //no [??] FFFFFF8C, not 15c23729

println( "-----" );

String g = "modules_newsfeeds/MenuBar/MenuBar.js";
String h = "modules_newsfeeds/ListBar/ListBar.js";

println( getHash(g) ); //yes [??] FFFFFF8C, not a15c23e5
println( getHash(h) ); //yes [??] FFFFFF8C, not a15c23e5

}
java c++ algorithm firefox hash
7个回答
5
投票

这里是算法的工作原理：

initialize hash to 0
for each byte
    shift hash 4 bits to left (with rotate)
    hash = hash XOR character

视觉上（16位版本）：

00110000             = '0'
    00110001         = '1'
        00110010     = '2'
            00110011 = '3'
0100            0011 = '4'
00110101             = '5'
====================
01000110001000010000  (and then this will be 'rotated'
                       so that it lines up with the end)
giving:
        00100001000001000110

这是什么意思，如果您具有相同长度的字符串，并且大多数情况下都相同，那么在至少一种情况下，一个字符的低4位和下一个字符的高4位或彼此必须唯一。但是，将32位数字粘贴到表中的方法可能更弱，这意味着它要求字符串中特定位置的下4位或上4位（mod 8个字符）是唯一的。

6
投票

根据我对阅读Bugzilla条目的了解，该错误会在出现两个明显的问题时显示出来：

  1. 他们的哈希算法会为“足够相似”的网址生成冲突。从错误“足够相似”看来，这意味着每4个字符（或8个字符）的网址是相同的，并且
  2. 它们处理哈希冲突的逻辑失败，因为它们尚未将具有相同哈希值的先前url刷新到磁盘。

因此，基本上，如果您的网页包含两个非常相似的网址，则可能会在某些版本的Firefox上发生。我希望它通常不会在不同的页面上发生，因为从那时起FF将有时间将条目刷新到磁盘上，从而避免了计时问题。

因此，如果您有多个资源（脚本，图像等）都从同一页面加载，请确保它们包含9个完全不同的字符。您可以确保这一点的一种方法是通过向查询字符串（忽略）附加随机数据，例如：

2
投票

此错误是我网站的主要问题：http://worldofsolitaire.com

我很早以前通过在.htaccess文件中使用条件规则来解决此问题，该规则将为Firefox用户禁用网站上所有图像的缓存。这是一件很恐怖的事情，但是当时我无法追踪Firefox中的错误，并且让网站稍微慢一点比显示重复/损坏的图像要好。

[当我阅读最新的Firefox版本中已修复的链接错误时，我于2009年4月19日（昨天）将条件更改为仅对Firefox 2用户禁用缓存。

[几个小时后，我收到Firefox 3用户的10封电子邮件（已确认），他们看到重复的图像。因此，此问题仍然是Firefox 3中的问题。

我决定创建一个简单的Linux测试程序，该程序可以让我检查URL以查看它们是否生成相同的缓存哈希键。

要在任何Linux系统中进行编译：g ++ -o ffgenhash ffgenhash.cpp

这里是代码（保存到文件ffgenhash.cpp中）

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define ULONG_MAX 0xFFFFFFFF
#define PR_ROTATE_LEFT32(a, bits) (((a) << (bits)) | ((a) >> (32 - (bits))))

unsigned long ffgenhash(const char * key)
{
    unsigned long h=0;

    for(const unsigned char * s = (unsigned char *) key; *s != '\0'; ++s)
    {
        h = PR_ROTATE_LEFT32(h, 4) ^ *s;
    }

    return (h==0 ? ULONG_MAX : h);
}

int main(int argc, char ** argv)
{
    printf("%d\n", ffgenhash(argv[1]));
    return 0;
}

如您所见，这是两个真实的URL，它们生成相同的缓存哈希键：

./ffgenhash "http://worldofsolitaire.com/decks/paris/5/12c.png"
1087949033
./ffgenhash "http://worldofsolitaire.com/decks/paris/5/13s.png"
1087949033

由于我在Javascript循环中预加载了这些图像，因此在此处无法尝试使用某种空的

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.