X-Gold 608 Unlock
The 3G software unlock proved more difficult than the previous unlocks due to the fact that the baseband bootloader is signature checked by the bootrom. The iPhone Dev Team has successfully unlocked baseband firmwares by overriding carrier locks on-the-fly in RAM, therefore at boot the baseband bootrom can validate the bootloader, and the bootloader can validate the baseband.
RAM Unlock History
On December 21, 2008, MuscleNerd demonstrated yellowsn0w, the first unlock. Originally, yellowsn0w was designed for basebands 02.04.03 and earlier, until geohot shared the AT+stkprof Exploit with them. On January 27, 2009, Apple released iOS 2.2.1, which contained baseband 02.30.03 and patched said exploit.
Oranav discovered another exploit (the AT+XLOG Vulnerability), and shared it with the iPhone Dev Team for the next unlock. The iPhone Dev Team kept it under wraps to target firmware 3.0 and the iPhone 3GS. The unlock, codenamed ultrasn0w, was released to the public on 23 June 2009 for baseband 04.26.08 only. 
iOS 3.1 contained a baseband 05.11.07, which patched the AT+XLOG Vulnerability. The AT+XEMN Heap Overflow was exploited in a new unlock named blacksn0w, released by geohot on 3 November 2009. A few months later, the vulnerability was patched in baseband 05.12.01.
When iOS 4.0 was publicly released, an updated release of ultrasn0w was released, using the AT+XAPP Vulnerability to unlock all basebands found in firmwares 3.0 through 4.0. Apple countered this with a baseband update in iOS 4.1.
- Find an exploit in the bootrom to break the chain of trust. The Dev-Team successfully dumped the bootrom, but they won't release it as it's copyrighted code.
- Improve by several orders of magnitude the NCK brute forcer, and find a way to extract the CHIPID and NORID
- Find the theorized algorithm of NCK generation
- Factorize the RSA keys used for signing
- Find a second preimage for a signature
- Use a SIM hack such as the TurboSIM Unlock
- Find a way to patch running memory to "unlock" the phone on every bootup. This is how ultrasn0w works.
- Find an exploit in the Baseband Bootloader so you can downgrade the baseband, then use ultrasn0w. Geohot and the iPhone Dev Team found (independently) an exploit in bootloader 5.8, but it isn't useful enough as only very-early (week<30) iPhone 3G units have bootloader 5.8.