Retry your path selection if you don't get an NTor-supporting relay in it?
Currently Tor chooses its path as normal, and then it decides for each relay whether it will send a TAP or NTor.
Coupled with the use of CREATE_FAST for the first hop, that means if you flip two (weighted) coins wrong, you're building a circuit that's worth attacking by an adversary who finds breaking 1024-bit crypto doable.
By my count, the current consensus aggregate weight for various relay versions is:
0.2.2.x: 351110 0.2.3.x: 4036995 0.2.4.x: 6361554 0.2.5.x: 285012
So oversimplifying grossly, that's a 40% squared = 16% chance of flipping those coins wrong given the current network.
But even in a world where 90% of the relay capacity has upgraded, that's still a 1% chance of an all-TAP circuit. Not so good.
(Implementing proposal 221 would help here, but not make the problem go away entirely.)
I think we should have a config option, probably set to auto and controlled by the consensus, to flip our coins again if we're not going to send an NTor cell to any of the relays in our path.
Unless we want to decide that users should always want it, and not even make it a config option or consensus param? I don't think we should do that at least until we've calculated the actual odds of all all-TAP path. They could actually be quite a bit higher than 16% now, since your Guards are discounted as a function of the scarcity of guard bandwidth, and a lot of middle relays are small and a lot of small relays haven't upgraded yet. In that case turning on this 'pick another path' feature could significantly impact anonymity too.
I wonder how sad 0.2.4 users would be if they don't get this feature. Probably pretty sad. So, setting to 0.2.4 but that's up for debate.