1

From an answer this earlier question: Does adding dictionary words to passwords weaken them?

"...you have no way to recognize it as a password before testing it (against a hash or an online service)"

This raises my question, for clarification: Can dictionary attacks and related tools get feedback about words or patterns, in order to solve in parts? If a cracking tool extracts the user's name elsewhere (say "Kim" for example) and tries it in a 20-character phrase, doesn't it still have to solve the exact 20-char phrase before gaining confirmation of the 3-char sequence and location? Do the hash analyses find patterns to explore?

Community
  • 1
antold
  • 21
  • 1
  • Umm.. it seems that you've started this question somewhere else and you're continuing the discussion here. Would you please provide some context? For starters, where did the first sentence come from? – Adi Apr 29 '13 at 19:13
  • if the hash is good there is no info about the password revealed in the hash (so the [password slot machine](http://tvtropes.org/pmwiki/pmwiki.php/Main/PasswordSlotMachine) only happens with bad hashing) – ratchet freak Apr 29 '13 at 19:18

2 Answers2

6

Proper cryptographic hash functions are all-or-nothing: you either get the exact correct input, to the last bit, or you get nothing. No patterns, no partial solving, no Mastermind-like cracking. That's why it is called brute force: there is no finesse whatsoever in password cracking.

Being able to solve passwords "partially" only happens in Hollywood movies, or in cases of blatant incompetence.

Community
  • 1
Tom Leek
  • 170,038
  • 29
  • 342
  • 480
  • So, it seems that there is little downside to burying something "common" or obvious in a pass phrase. – antold Apr 29 '13 at 20:05
  • The downside of adding "obvious" words in the password is that they don't add much to security, but you still have to type them when you use them. This becomes a problem if this incites the user to shorten the "non-obvious" parts of his password. – Tom Leek Apr 29 '13 at 20:13
  • Maybe brute force is applied in sections: Words, phrases, sentences, common word-number combos, words w common symbol substitutes... A phrase could last longer against cracking, just by luck, if an attack starts with a different category of guessing. – antold Apr 29 '13 at 20:25
  • As per my previous comment: It seems an attack would be structured based on various criteria. It may guess a "lucky" course and start from the right shore, to succeed more quickly. Otherwise, don't all passwords have equal value if drawn from the same char-set and having the same # of characters? – antold Apr 29 '13 at 20:43
3

Remember combination locks?

Combination lock

With combination locks, assuming they don't suffer a major design flaw and the attacker doesn't posses x-ray vision, is impossible to determine if the tried combination is a partial match to the preset unlock combination. The other lock rings that aren't in their unlocked position will prevent you to unlock all of it, but you have no way of determining which lock ring is in which position either. Pretty neat IMHO.

Ideal cryptographic hash functions (the ones that don't suffer from hash collisions, i.e. are collision resistant) work in the same way. Change one password character, and there's no way of determining a mathematical equation that will also take a previous hash value as input, and compute the next one. That's why cryptographic hash functions are also considered one-way functions. We know how to compute hash values given some value as an input, but we have no way of reversing these functions to work the other way, too. At least not for the time being.

Food for thought: We can't really prove some function is one-way, we can only prove that it isn't.

Matthew
  • 27,263
  • 7
  • 89
  • 101
TildalWave
  • 10,801
  • 11
  • 46
  • 85
  • 2
    To be precise, it is not necessarily impossible to prove a function to be one-way. It is just that, right now, we do not know how to prove any function to be one-way; but that does not mean that one-wayness is inherently non-provable. Also, we do not know whether a one-way function can actually exist at all; there again, we have no proof one way or another. – Thomas Pornin Apr 29 '13 at 20:43
  • @ThomasPornin - Exactly, but I didn't want to cause unnecessary self-implosion of the reader's brain, so I simplified it to the level I believe is sufficient for understanding of this presented paradigm. :) – TildalWave Apr 29 '13 at 20:58
  • "assuming they don't suffer a major design flaw" spoiler: most combination locks *do* suffer from "major design flaws". – Peter Green Mar 30 '21 at 00:26