Some guys in Istambul, Turkey posted a video demonstration of a hardware hack that will downgrade the Baseband to 04.26. Downgrading the baseband, means that you can use the old ( current ) unlock tools. Now all you need to do is take a trip to Istambul or, maybe, you can do it yourself. Do you feel lucky,punk?
Hardware Unlock Of iPhone 3G Running OS 3.1.3 [video]
