How vulnerable are passphrases with grammatical structure?

Question

Imagine I create a passphrase using random dictionary words but a common grammatical structure (eg: article, noun, verb, adjective, noun). Given a pretty small dictionary of 5000 words, how vulnerable are such phrases compared to:

1. passwords with the usual recommendation of 8-16 characters, upper, lower, numbers
2. some phrase you make up yourself based on your favourite book, poem, quote, or whatever
3. diceware style phrases (5 random words stuck back-to-back)
4. the PGP recommendation of "shocking nonsense" (which is similar to what I'm doing)

A few examples of what I'm thinking of:

its headlock fumbled my angle
should its mimosa withstand an oath
a harpoon might expertly staff our ratios
the Sumerian ambushes the tiny murmur

Are there known ways to attack such passphrases beyond checking for common words first in a brute force attack? Can you think of a better way than this?

How effective would Markov Chains or n-grams be based on large word corpus's (eg: Google Web or Brown)? My gut feel is the 'nonsense' nature of the phrases would mitigate many common chains of words, but is there any research or off-the-shelf cracker I could use to verify that?

Effect of Grammar on Security of Long Passwords is relevant, they even highlight a nonsense passphrase of their own as unexpectedly good (hammered arsine requirements), but my understanding of their paper is they're trying most common words first. This question is also relevant.

^{Full disclosure: I'm developing a passphrase generator which uses this grammatical technique to assist memorisation, but still keeping the words used random. I'm interested in some critique of my algorithm, while still fitting within the Q&A style of Stack Overflow.}

Answer 1

The major finding of the paper you linked is that grammatical sentences do not have the entropy you'd expect from sentences of that length. A reasonable response to that would be to just not count the words you're adding to make the sentence 'correct'; choosing one of your examples a harpoon might expertly staff our ratios should be considered about as strong as harpoon expertly staff ratios.

If you're looking for maximum password strength; you should also avoid words that follow grammatical rules, from the paper:

Grammatical structures, or tag-rules, split the password search space unevenly; the size of the search space of individual tag-rules are different e.g. the size of “Noun Noun” is greater than the size of “Adjective Noun”.

Implying that you should avoid 'adjective noun' to maximise your entropy. This is true even if your algorithm generates them randomly, as the structure functions to compress the password. It's also worth noting that the paper didn't look for pairs that made sense together (watery scissors would have been tried).

The point in the paper of choosing common words first wouldn't decrease its effectiveness against random, but approximately correctly formed, sentences; you can always design your dictionary to distribute words randomly by frequency. It's not so much that they try common words first, but that they try groups that are often seen together, together.

There has also been some research on the Markov model you suggest; it may be worth running that sort of analysis over the password you generate before presenting it to the user?

You may find the answers in this related question of interest.