During padding oracle attack (CBC), how is first byte of plaintext block is obtained? Imagine conducting a padding oracle attack against CBC mode with 16-byte length blocks, and PKCS#5 used for padding.

You start, as always, revealing the last byte of plaintext. Then you iteratively move backward and reach the first byte of last plaintext block. At this stage, you already spoofed the padding with 15 bytes, which values are 0x0f.


So, how do you reveal the first byte of a block, since you’re out of padding length?
Does PKCS#5 allow you to pad 16 bytes with 0x10 value?
Or, these things are up to the implementation of padding used in a specific application?
Does PKCS#5 allow you to pad 16 bytes with 0x10 value?


No, but that's because PKCS#5 only specifies padding for DES, and that has an 8 byte block size. Even PKCS#5 itself refers to PKCS#7 when it comes to padding AES. More information about the differences here.

Now for the real answer. PKCS#7 padding, which is identical to PKCS#5 but allows any block size, requires 16 times the 0x10 byte value as padding:


  For such algorithms, the method shall be to pad the input at the
  trailing end with $k - (l \bmod k)$ octets all having value
  $k - (l \bmod k)$, where $l$ is the length of the input.


Here $k$ is the block size of the block cipher in bytes, for instance AES with a block size of 16 bytes. Now obviously if $l$ is a multiple of 16 then then a full block of padding is added (as $l \bmod k$ would evalulate to zero and therefore only $k$, i.e. 16 would be left).

The reason for this is simple: imagine that a plaintext message that is a multiple of the block size ends with a valid padding pattern. Then the unpadding would remove that part of the message. By always performing padding the unpadding can be performed regardless of the contents and size of the message (i.e. allowing any message to be decrypted correctly).