OASIS Open Document Format for Office Applications (OpenDocument) TC

I don't believe increasing the length of the hash significantly helps a rainbow table attack.

I'll ask some of the cryptographers and find out.

Dennis is quite correct that it isn't what the password protects, but the password itself that is of value.


Sent from my phone, but I might be verbose - I have a keyboard...



                                                

					
                                                    

        
                                                
				
                                                

                                                    
                                                
                                                
                                            

From a quick read of the Wikipedia entry, and some of the references, it seems that increasing the hash output size actually causes a Rainbow table to become _more_ effective, not less. Seems that collisions play havoc with Rainbow tables, though there are modern techniques that reduce the chance of a collision actually being a problem. 

And collisions aren't really a big problem for most passwords given a modern hashing algorithm. Most user-chosen passwords would fit into upper and lower case alpha, plus numbers, assume a length of 10 characters. There's only 59 bits of total keyspace there, well below the 160-bit keyspace of sha-1, making the chance of a collision neglible, even if sha-1 deteriorates to something smaller. To even start to see collisions, you need to be dealing with full-keyboard character sets, and password lengths up around 22 characters, _and_ they have to have not reduced entropy by including words.

This means that collisions weren't a problem to start with, so going to sha-256 is fixing part of the problem that isn't broken. It is nice to use hashing algorithms that are recommended by NIST, the EU, etc, so there is some value in using sha-256, but it doesn't help protect the password at all.

Oddly enough, a really bad hash can be of some benefit if you're attempting to protect the password. If you have a lot of collisions, you may find _a_ password that works, but perhaps not _the_ password that we started with.

Another aspect of the hash length problem is to consider this - a sha-256 hash might be around 2-4x slower to compute than a sha-1 hash. A single hash brute-force attack can get up around 100 million cracks/second. This means an 8-character all lower case password would fall in 15 minutes on average, 30 minutes max. If you can drive down the cracks/sec by using an iterated hash, you can remove much of the attacker's ability to run computations in parallel, and get the crack rate down to around 10,000 hashes/second. This would hold up for an average of 120 days.  Add in sufficient salt, and you remove the Rainbow table attack as well.

My recommendation is to use a real key derivation function to create a password verifier. It can be a bit of a problem to deal with versioning - if you change this, then an older version of the software obviously cannot verify the password. However, due to the severity of disclosing passwords, I'd tend to recommend against implementing a feature that exposes passwords in that manner.

Just how widespread is this past usage? I do not recall seeing it in the v1.1 spec, but I may have missed it. If this is something new to this version, I'd strongly recommend doing it right, even if there are existing implementations.

________________________________________
From: David LeBlanc [dleblanc@exchange.microsoft.com]
Sent: Saturday, October 30, 2010 2:57 PM
To: dennis.hamilton@acm.org; 'ODF TC List'
Subject: RE: [office] The problem of visible hashes for protection keys

I don't believe increasing the length of the hash significantly helps a rainbow table attack.

I'll ask some of the cryptographers and find out.

Dennis is quite correct that it isn't what the password protects, but the password itself that is of value.


Sent from my phone, but I might be verbose - I have a keyboard...



                                                

					
                                                    

        
                                                
				
                                                

                                                    
                                                        
                                                        Original Message
                                                
                                                Original Message-----
From: Dennis E. Hamilton 

Nice analysis.  Thanks David,

Here are the places in ODF 1.1, with the attribute always storing a
key-verification hash (now documented in ODF 1.2 as being SHA-1):

4.4.1 Section Attributes, Protected Section subsection, text:protection-key
attribute

8.1.1 Table Element, Protected subsection, table:protection-key attribute

8.5.1 Document Protection, table:protection-key attribute [applies to
spreadsheets]

By virtue of sharing the sectionAttr RNG pattern defined in 4.4.1,
protection keys are also allowed on the following elements: 7.3.2

There is a mistake in the previous note.  There is a

Just specifying a digest algorithm is a fairly major flaw. I believe that xml-enc has a way to express a real KDF. One aspect of this that has to be done is to not only specify the digest algorithm, but also the iteration count, so that future versions can increase the iteration count, and older versions can still consume it.

At the very least, you need something along these lines:

We only have the two attributes, *:protection-key and
*:protection-key-digest-algorithm.  However, I think we had loosened what
:protection-key carries as being the information for verifying a key, not
always a direct hash of the key.  This would allow us to register algorithms
beside the normal ones that specified a PBKDF2 method where the
protection-key entry would encode the iteration count and a salt as well as
the derived key used as the authenticator.  So we have an opening.  The
language wasn't loosened up completely (it is a bit contradictory) so I am
going to see if I can put in a quick fix.

I think adding a child element that handled the protection key would be too
much of a stretch.  There is no digest-algorithm URI for PBKDF2 that works
for this.  I looked before when digging into the encryption options for ODF
1.2.



                                                

					
                                                    

        
                                                
				
                                                

                                                    
                                                        
                                                        Original Message
                                                
                                                Original Message-----
From: David LeBlanc [mailto:dleblanc@exchange.microsoft.com] 
Sent: Saturday, October 30, 2010 19:29
To: dennis.hamilton@acm.org; 'ODF TC List'
Subject: RE: [office] The problem of visible hashes for protection keys

Just specifying a digest algorithm is a fairly major flaw. I believe that
xml-enc has a way to express a real KDF. One aspect of this that has to be
done is to not only specify the digest algorithm, but also the iteration
count, so that future versions can increase the iteration count, and older
versions can still consume it.

At the very least, you need something along these lines:

All excellent points, of course.  But in 12 hours now one will remember or 
find what you said, unless this was entered into JIRA.

-Rob

"Dennis E. Hamilton" 

David,

> I do not know if there's an algorithm URI for PBKDF2, but seems like there ought to be.

There is one in XML-ENC 1.1:  http://www.w3.org/2009/xmlenc11#pbkdf2

(or did you mean in the ODF spec ?)


Best regards

Bart

Bart, David, and Rob

I see this on-list exchange as a matter of mutual education on the context
and what the existing provisions are.  There is no particular problem
although there are a couple of wordings in CD05 that reflect incomplete
resolutions of some issues (some effected wordings were not caught in the
resolution).  

There were previous issues on this topic and I also did considerable
analysis.  There might need to be a branch off of a previously-resolved
issue to correct some small glitches that have crept into later drafts of
ODF 1.2 where it can be seen that the application of previous resolutions
needs further adjustment (e.g., remove contradictions because a related
paragraph was left unchanged).  But the intention has already been reflected
in existing JIRA issues, and the adjustments I see now are quite
straightforward.

   *   *   *   *   *   *   *   *

With regard to having a URI for PBKDF2, the problem is that PBKDF2 is not a
single method, it is a framework of methods.  Finally, there is no mention
of PBKDF2 in [xmlenc-core], which is what we have been using.

PBKDF2 requires a supplied Pseudo-Random Function (typically an HMAC but it
can be one of many) and there are specifications that are needed with regard
to the size of the key to be produced (PBKDF2 can produce very large keys in
terms of bits, in terms of entropy, different story).  Finally, there are
whatever the input conditioning/constraint is for starting up a PBKDF2.
PBKDF2 specifications (in RSA documents and NIST materials, as I recall)
deal with the internal padding operations that are required and how data
passes to successive iteration stages.  It matters what conditioning is done
for the password that PBKDF2 starts with.  For Blowfish CFB, the password is
turned into a start key using SHA1, and that is used in the PBKDF2 as the
password from which the key is derived.   This is a pre-PBKDF2 convention
and not part of PBKDF2 which can start with a password of pretty much any
length and do its own conditioning to get down to the size used in the
iterations.

There is an xmlenc-core1 currently in Working Draft, so we can't reference
it, 

What's the issue number tracking this?



                                                

					
                                                    

        
                                                
				
                                                

                                                    
                                                        
                                                        Original Message
                                                
                                                Original Message-----
From: Dennis E. Hamilton [mailto:dennis.hamilton@acm.org] 
Sent: Sunday, October 31, 2010 10:20 AM
To: 'Hanssens Bart'; 'ODF TC List'
Cc: Rob Weir; David LeBlanc
Subject: Visible Hashes and PBKDF2

Bart, David, and Rob

I see this on-list exchange as a matter of mutual education on the context and what the existing provisions are.  There is no particular problem although there are a couple of wordings in CD05 that reflect incomplete resolutions of some issues (some effected wordings were not caught in the resolution).  

There were previous issues on this topic and I also did considerable analysis.  There might need to be a branch off of a previously-resolved issue to correct some small glitches that have crept into later drafts of ODF 1.2 where it can be seen that the application of previous resolutions needs further adjustment (e.g., remove contradictions because a related paragraph was left unchanged).  But the intention has already been reflected in existing JIRA issues, and the adjustments I see now are quite straightforward.

   *   *   *   *   *   *   *   *

With regard to having a URI for PBKDF2, the problem is that PBKDF2 is not a single method, it is a framework of methods.  Finally, there is no mention of PBKDF2 in [xmlenc-core], which is what we have been using.

PBKDF2 requires a supplied Pseudo-Random Function (typically an HMAC but it can be one of many) and there are specifications that are needed with regard to the size of the key to be produced (PBKDF2 can produce very large keys in terms of bits, in terms of entropy, different story).  Finally, there are whatever the input conditioning/constraint is for starting up a PBKDF2.
PBKDF2 specifications (in RSA documents and NIST materials, as I recall) deal with the internal padding operations that are required and how data passes to successive iteration stages.  It matters what conditioning is done for the password that PBKDF2 starts with.  For Blowfish CFB, the password is turned into a start key using SHA1, and that is used in the PBKDF2 as the
password from which the key is derived.   This is a pre-PBKDF2 convention
and not part of PBKDF2 which can start with a password of pretty much any length and do its own conditioning to get down to the size used in the iterations.

There is an xmlenc-core1 currently in Working Draft, so we can't reference it, 

Here are the issues that I've tracked about *:protection-key and
*:protection-key-digest-algorithm [no -name, I misspoke in my "medley" post
to the list]. These are in order by the section of ODF 1.2 CD05 Part 1 that
is involved.  These changes leave room for introduction of smarter
key-verification algorithms and their supporting data, but do not specify
any smarter ones.  I figured we needed to have a way to develop improved
techniques, their specification, and their agreed use over the life of ODF
1.2 and beyond.  The adaption of a PBKDF2 technique as a password verifier
was beyond my imagining, but I can see it used by mutual agreement and
implementation-defined profile, building on the provisions that are in ODF
1.2.

 - Dennis

19.698.4 table:protected attribute of