Increasing the difficulty to guess values using random digit position choices An online service I use sent me a passcode of 6 digits. 000000 - 999999.
When I am required to use this passcode to access my account the service asks for three of the digits from the six they sent.
On each load of the sign in page the three digits they ask for are randomly selected and displayed in the order they are selected. So it could be digits 1, 2 and 4 for the first load, then 5, 2 and 6 for the second and so on.
Now imagine I have forgotten the passcode:
If the passcode was entered in plaintext with the characters in the in order to have a 100% chance of accessing the account I would have to enter 1 000 000 passcodes.
Given the above defined requirements of passcode entry how many times would I have to try in order to have a 100% chance of entering the account, or indeed, is 100% even achievable considering the part of the mechanism that chooses randomly on each load?
If it is achievable, what is the effect of displaying the randomly selected required digits in the order they fall rather than numeric order?
PS ... if you are interested there is a collection of questions on ux.stackexchange.com that have brought me here, fundamentally I am wondering how difficult something can be made for a bruteforce password attack while keeping the actual code as simple as possible for the user. An example question: https://ux.stackexchange.com/questions/51379/should-password-be-set-by-users-without-security-check/51486#51486
 A: Your company tell you which three digits of the passcode they want, so they could ask for digits $(1,2,3)$, or digits $(2,5,6)$, and so on. Each set of three digits must therefore be in the set $000-999$. Obviously, if they chose the same set of $3$ digits each time (so they asked you over and over again for the first three digits) you could make it within $1000$ guesses.  
Now suppose you can keep track of which digits they've asked for - just do the $1000$ passcodes check for each set they ask for, and start again every time they ask you for a different set of digits. For example, suppose they asked you for digits $(1,2,3)$, then $(2,3,4)$, then $(2,5,6)$ and then $(2,3,4)$ again. You would guess $000$ for the first three, then $001$ for the last one (since you've already guessed $000$). By the pigeonhole principle (you can google this if you haven't heard of it) we must eventually try every combination - in the worst case this is when we try $1000$ combinations for every possible triplet of digits.  
The number of possible triplets follows a simple counting argument: we could choose any of the $6$ numbers for the first place, then $5$ for the second, and $4$ for the third - so there are $120$ possible triplets, but notice that if we had the triple $(1,2,3)$ and $(2,3,1)$ these are essentially the same, so we want to account for ordering as well - there are $6$ ways of reordering each triplet, so there are $120/6=20$ different triplets. Therefore you only have $20,000$ combinations to try!
A: An upper bound $7482$ for the optimal number can be found (that is, we can show that $7428$ guesses suffice but don't know if it can be done in a smaller number of steps) by studying this algorithm, which probably isn't optimal:


*

*Let $S$ be the set of all possible passcodes.

*Read the requested indices $i_0$, $i_1$, $i_2$.

*Select values $a_0$, $a_1$, $a_2$ that maximize the size of the set $S'=\{c \in S : c_{i_0}=a_0 \wedge c_{i_1}=a_1 \wedge c_{i_2}=a_2\}$.

*Try values $a_0$, $a_1$, $a_2$. If they work, we are done. If they don't work, we know that the passcodes in $S'$ are not possible, so remove the passcodes of $S'$ from $S$ and go to step 2.
Some analysis:
Let $s_i$ be the size of $S$ after the $i$th step, so $s_0=1000000$ and if $s_{N-1}=1$, we know that we guess right at the $N$th step because only one possible passcode is remaining.
Because there are $10^3$ possible choices for $(a_0,a_1,a_2)$, by the pigeonhole principle we know that $|S'|\geq \left\lceil \frac{S}{10^3}\right\rceil$. Therefore, we know that
$$
s_{i+1} \leq s_i - \left\lceil \frac{s_i}{10^3}\right\rceil.
$$
The sequence $(s_i)_i$ is bounded above by the sequence $(t_i)_i$ defined by
$$
t_0=1000000,\\
t_{i+1} = t_i - \left\lceil \frac{t_i}{10^3}\right\rceil
$$
For this, we get that $t_{7482}=0$, which gives the upper bound.
A: Since on each load of the sign in page you are asked to fill in $3$ digits from $0$ to $9$ the probability to succeed is $\frac{1}{10^3}$ on that particular scenario. However, there are $6·5·4$ ways the system can select these digits for you to guess. If $A_i = \{\mbox{"tuple $i$ is asked"}\}$ then:
$$P(\mbox{"enter account"}) = \sum_{i = 1}^{6·5·4} P(\mbox{"enter account"} | A_i)P(A_i) = \sum_{i = 1}^{6·5·4} \frac{1}{10^3}\frac{1}{6·5·4}$$
So $P(\mbox{"enter account"}) = \frac{1}{10^3}$, which is consistent with what we would expect, given that any tuple of digits has the same chance to be selected by the system.
