> To my knowledge, these are usually dictionary-based attacks, which would significantly decrease the "search space" to discover even a long, lower-case sentence.
The xkcd comic assumes a dictionary-based attack. It points out that choosing 4 words at random from the 2048 most common words provides more entropy than choosing one word at random from the most common 65536 words and performing some letter substitutions on it. In both cases, it is assumed the attacker knows the formula used to create the password.
If your formula for creating a password is "Choose a printable ASCII character at random, then repeat", you only need a password that is 7 characters long to beat the "4 random common words" formula (95^7 > 2048^4). But the percentage of people who construct passwords by choosing random printable characters rounds to zero.
The xkcd comic assumes a dictionary-based attack. It points out that choosing 4 words at random from the 2048 most common words provides more entropy than choosing one word at random from the most common 65536 words and performing some letter substitutions on it. In both cases, it is assumed the attacker knows the formula used to create the password.
If your formula for creating a password is "Choose a printable ASCII character at random, then repeat", you only need a password that is 7 characters long to beat the "4 random common words" formula (95^7 > 2048^4). But the percentage of people who construct passwords by choosing random printable characters rounds to zero.