Consider AES-256, 128-bit blocks, and PKCS#5 Padding.
During a Padding Oracle Attack, a manipulated byte of cipher text is sent to the oracle and we eventually hope to find out what that respective byte of plaintext was.
If I know the set of possible characters in the plaintext will only be lowercase english letters, then is there any way in which I can speed up the deciphering process? If so, then specifically what would this look like?
I will assume you generally understand the mechanics of the padding oracle attack. Say we have some ciphertext block $c_i = c_{i-1} \oplus E(k,m_i)$ and we want to find the last byte of $m_i$. Let $b$ denote the last byte of $m_i$, which we are trying to find.
Consider ciphertexts of the form $(c_{i-1} \oplus \texttt{00} \cdots \texttt{00} g,c_i)$, where $g$ is a single byte. Such a ciphertext decrypts to $m_i$, except the last byte has been changed from $b$ to $b \oplus g$. When the server decrypts, it sees a string that ends in byte $b \oplus g$ --- does this string have valid padding? In most cases, it has valid padding only when $b \oplus g = \texttt{01}$ (lets assume that $m_i$ doesn't end in $\cdots \texttt{02}\,b$ or $\cdots \texttt{0303}\,b$, etc). When the server tells us which choice of $g$ leads to valid padding, we can solve for $b = \texttt{01} \oplus g$.
If you know that $b$ is one of only 26 possible values, then there are only 26 possible values of $g$ that you need to try -- compared to the general case where you have to try all 256 choices of byte $g$. I only mentioned the case of finding the last byte of the plaintext, but the same logic applies for any byte.
If I know the set of possible characters in the plaintext will only be lowercase English letters, then is there any way in which I can speed up the deciphering process? If so, then specifically what would this look like?
Yes, it helps. First, remember that the padding oracle works on the fact that the server sends back only one information at all; the padding incorrect.
In the padding oracle, one modifies the bytes of the previous ciphertext $C_{n-1}$ and hopes that the server doesn't return the padding incorrect. What we send the server is the IV plus whole ciphertext with the updated $C_{n-1}$ hoping that it will leak information on the last block $C_n$. ( Well that is only for the last block. In the Padding oracle attack, actually, the sever is a decryption oracle that can be used to decrypt all blocks).
The decryption $S_n = Dec(k, C_n)$ has no control under the attacker. That is going to be used to reveal the last block on the server-side; $P_n = S_n \oplus C_{n-1}$.
Although the attacker doesn't know the $S_n$ they can set the bytes of the $C_{n-i}$ to so that $P_n$ is in the range small and capital letters plus the padding bytes from 0x00 to 0x10 ( 16-byte length block cipher like the AES). We can see this from;
m is in the 26 message characters
r is random
x is not known random
P_n = ..............m
-----------------------
S_n = ..............x
x-or
C_n-1 = ..............r
We know the equation $ P_n = S_n \oplus C_{n-1}$ we can use the 26 characters to modify the equation by $$m \oplus t = \texttt{0x01}.$$ The 26 different values for the $t$ is enough to test the last padding. The other positions are similar.
