Enhanced PHP File Manager

⬆️ Go Up (..)

📊 Server Information

Server:

nginx/1.28.0

System:

Linux 6.8.0-90-generic

PHP Version:

8.4.15

User:

alqudsvolunteers

Directory:

/home/alqudsvolunteers/rootlink/proc/self/root/proc/thread-self/root/usr/share/doc/varnish/html/phk

Free Space:

79.92 GB

🔧 Quick Actions

✏️ Editing: varnish_does_not_hash.html

<!DOCTYPE html>

<title>Varnish Does Not Hash &#8212; Varnish version 7.5.0 documentation</title>
    <link rel="stylesheet" type="text/css" href="../_static/pygments.css?v=fa44fd50" />
    <link rel="stylesheet" type="text/css" href="../_static/classic.css?v=e2714048" />
    
    <script src="../_static/documentation_options.js?v=8214db13"></script>
    <script src="../_static/doctools.js?v=888ff710"></script>
    <script src="../_static/sphinx_highlight.js?v=dc90522c"></script>
    
    <link rel="index" title="Index" href="../genindex.html" />
    <link rel="search" title="Search" href="../search.html" />
    <link rel="next" title="The Tools We Work With" href="thetoolsweworkwith.html" />
    <link rel="prev" title="Why HTTP/2.0 does not seem interesting" href="http20.html" /> 
  </head><body>
    <div class="related" role="navigation" aria-label="related navigation">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="../genindex.html" title="General Index"
             accesskey="I">index</a></li>
        <li class="right" >
          <a href="thetoolsweworkwith.html" title="The Tools We Work With"
             accesskey="N">next</a> |</li>
        <li class="right" >
          <a href="http20.html" title="Why HTTP/2.0 does not seem interesting"
             accesskey="P">previous</a> |</li>
        <li class="nav-item nav-item-0"><a href="../index.html">Varnish version 7.5.0 documentation</a> &#187;</li>
          <li class="nav-item nav-item-1"><a href="index.html" accesskey="U">Poul-Hennings random outbursts</a> &#187;</li>
        <li class="nav-item nav-item-this"><a href="">Varnish Does Not Hash</a></li> 
      </ul>
    </div>

<div class="document">
      <div class="documentwrapper">
        <div class="bodywrapper">
          <div class="body" role="main">
            
  <section id="varnish-does-not-hash">
<span id="phk-varnish-does-not-hash"></span><h1>Varnish Does Not Hash<a class="headerlink" href="#varnish-does-not-hash" title="Link to this heading">¶</a></h1>
<p>A spate of security advisories related to hash-collisions have made
a lot of people stare at Varnish and wonder if it is affected.</p>
<p>The answer is no, but the explanation is probably not what most of
you expected:</p>
<p>Varnish does not hash, at least not by default, and
even if it does, it’s still as immune to the attacks as can be.</p>
<p>To understand what is going on, I have to introduce a concept from
Shannon’s information theory: “entropy.”</p>
<p>Entropy is hard to explain, and according to legend, that is exactly
why Shannon recycled that term from thermodynamics.</p>
<p>In this context, we can get away with thinking about entropy as how
much our “keys” differ:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span>Low entropy (1 bit):
        /foo/bar/barf/some/cms/content/article?article=2
        /foo/bar/barf/some/cms/content/article?article=3

High entropy (65 bits):
        /i?ee30d0770eb460634e9d5dcfb562a2c5.html
        /i?bca3633d52607f38a107cb5297fd66e5.html
</pre></div>
</div>
<p>Hashing consists of calculating a hash-index from the key and
storing the objects in an array indexed by that key.</p>
<p>Typically, but not always, the key is a string and the index is a
(smallish) integer, and the job of the hash-function is to squeeze
the key into the integer, without losing any of the entropy.</p>
<p>Needless to say, the more entropy you have to begin with, the more
of it you can afford to lose, and lose some you almost invariably
will.</p>
<p>There are two families of hash-functions, the fast ones, and the good
ones, and the security advisories are about the fast ones.</p>
<p>The good ones are slower, but probably not so much slower that you
care, and therefore, if you want to fix your web-app:</p>
<dl class="simple">
<dt>Change::</dt><dd><p>foo=somedict[$somekey]</p>
</dd>
<dt>To::</dt><dd><p>foo=somedict[md5($somekey)]</p>
</dd>
</dl>
<p>and forget about the advisories.</p>
<p>Yes, that’s right: Cryptographic hash algorithms are the good ones,
they are built to not throw any entropy away, and they are built to
have very hard to predict collisions, which is exactly the problem
with the fast hash-functions in the advisories.</p>
<section id="what-varnish-does">
<h2>What Varnish Does<a class="headerlink" href="#what-varnish-does" title="Link to this heading">¶</a></h2>
<p>The way to avoid having hash-collisions is to not use a hash:  Use a
tree instead. There every object has its own place and there are no
collisions.</p>
<p>Varnish does that, but with a twist.</p>
<p>The “keys” in Varnish can be very long; by default they consist of:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">sub</span> <span class="n">vcl_hash</span> <span class="p">{</span>
    <span class="n">hash_data</span><span class="p">(</span><span class="n">req</span><span class="o">.</span><span class="n">url</span><span class="p">);</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">req</span><span class="o">.</span><span class="n">http</span><span class="o">.</span><span class="n">host</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">hash_data</span><span class="p">(</span><span class="n">req</span><span class="o">.</span><span class="n">http</span><span class="o">.</span><span class="n">host</span><span class="p">);</span>
    <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
        <span class="n">hash_data</span><span class="p">(</span><span class="n">server</span><span class="o">.</span><span class="n">ip</span><span class="p">);</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="p">(</span><span class="nb">hash</span><span class="p">);</span>
<span class="p">}</span>
</pre></div>
</div>
<p>But some users will add cookies, user identification and many other
bits and pieces of string in there, and in the end the keys can be
kilobytes in length, and quite often, as in the first example above,
the first difference may not come until pretty far into the keys.</p>
<p>Trees generally need to have a copy of the key around to be able
to tell if they have a match, and more importantly to compare
tree-leaves in order to “re-balance” the tree and other such arcanae
of data structures.</p>
<p>This would add another per-object memory load to Varnish, and it
would feel particularly silly to store 48 identical characters for
each object in the far too common case seen above.</p>
<p>But furthermore, we want the tree to be very fast to do lookups in,
preferably it should be lockless for lookups, and that means that
we cannot (realistically) use any of the “smart” trees which
automatically balance themselves, etc.</p>
<p>You (generally) don’t need a “smart” tree if your keys look
like random data in the order they arrive, but we can pretty
much expect the opposite as article number 4, 5, 6 etc are added
to the CMS in the first example.</p>
<p>But we can make the keys look random, and make them small and fixed
size at the same time, and the perfect functions designed for just
that task are the “good” hash-functions, the cryptographic ones.</p>
<p>So what Varnish does is “key-compression”:  All the strings fed to
hash_data() are pushed through a cryptographic hash algorithm called
SHA256, which, as the name says, always spits out 256 bits (= 32
bytes), no matter how many bits you feed it.</p>
<p>This does not eliminate the key-storage requirement, but now all
the keys are 32 bytes and can be put directly into the data structure:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">struct</span> <span class="n">objhead</span> <span class="p">{</span>
        <span class="p">[</span><span class="o">...</span><span class="p">]</span>
        <span class="n">unsigned</span> <span class="n">char</span>           <span class="n">digest</span><span class="p">[</span><span class="n">DIGEST_LEN</span><span class="p">];</span>
<span class="p">};</span>
</pre></div>
</div>
<p>In the example above, the output of SHA256 for the 1 bit difference
in entropy becomes:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span>/foo/bar/barf/some/cms/content/article?article=2
-&gt; 14f0553caa5c796650ec82256e3f111ae2f20020a4b9029f135a01610932054e
/foo/bar/barf/some/cms/content/article?article=3
-&gt; 4d45b9544077921575c3c5a2a14c779bff6c4830d1fbafe4bd7e03e5dd93ca05
</pre></div>
</div>
<p>That should be random enough.</p>
<p>But the key-compression does introduce a risk of collisions, since
not even SHA256 can guarantee different outputs for all possible
inputs:  Try pushing all the possible 33-byte files through SHA256
and sooner or later you will get collisions.</p>
<p>The risk of collision is very small however, and I can all but
promise you, that you will be fully offset in fame and money for
any inconvenience a collision might cause, because you will
be the first person to find a SHA256 collision.</p>
<p>Poul-Henning, 2012-01-03</p>
</section>
</section>

<div class="clearer"></div>
          </div>
        </div>
      </div>
      <div class="sphinxsidebar" role="navigation" aria-label="main navigation">
        <div class="sphinxsidebarwrapper">
  <div>
    <h3><a href="../index.html">Table of Contents</a></h3>
    <ul>
<li><a class="reference internal" href="#">Varnish Does Not Hash</a><ul>
<li><a class="reference internal" href="#what-varnish-does">What Varnish Does</a></li>
</ul>
</li>
</ul>

</div>
  <div>
    <h4>Previous topic</h4>
    <p class="topless"><a href="http20.html"
                          title="previous chapter">Why HTTP/2.0 does not seem interesting</a></p>
  </div>
  <div>
    <h4>Next topic</h4>
    <p class="topless"><a href="thetoolsweworkwith.html"
                          title="next chapter">The Tools We Work With</a></p>
  </div>
  <div role="note" aria-label="source link">
    <h3>This Page</h3>
    <ul class="this-page-menu">
      <li><a href="../_sources/phk/varnish_does_not_hash.rst.txt"
            rel="nofollow">Show Source</a></li>
    </ul>
   </div>
<div id="searchbox" style="display: none" role="search">
  <h3 id="searchlabel">Quick search</h3>
    <div class="searchformwrapper">
    <form class="search" action="../search.html" method="get">
      <input type="text" name="q" aria-labelledby="searchlabel" autocomplete="off" autocorrect="off" autocapitalize="off" spellcheck="false"/>
      <input type="submit" value="Go" />
    </form>
    </div>
</div>
<script>document.getElementById('searchbox').style.display = "block"</script>
        </div>
      </div>
      <div class="clearer"></div>
    </div>
    <div class="related" role="navigation" aria-label="related navigation">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="../genindex.html" title="General Index"
             >index</a></li>
        <li class="right" >
          <a href="thetoolsweworkwith.html" title="The Tools We Work With"
             >next</a> |</li>
        <li class="right" >
          <a href="http20.html" title="Why HTTP/2.0 does not seem interesting"
             >previous</a> |</li>
        <li class="nav-item nav-item-0"><a href="../index.html">Varnish version 7.5.0 documentation</a> &#187;</li>
          <li class="nav-item nav-item-1"><a href="index.html" >Poul-Hennings random outbursts</a> &#187;</li>
        <li class="nav-item nav-item-this"><a href="">Varnish Does Not Hash</a></li> 
      </ul>
    </div>
    <div class="footer" role="contentinfo">
    &#169; Copyright 2010-2014, Varnish Software AS.
      Created using <a href="https://www.sphinx-doc.org/">Sphinx</a> 7.2.6.
    </div>
  </body>
</html>

❌ Cancel

🗂️ Enhanced PHP File Manager

📊 Server Information

🔧 Quick Actions

✏️ Editing: varnish_does_not_hash.html

📤 Upload File

📁 Create Folder

📄 Create File

✏️ Rename Item

🗑️ Delete Confirmation