As soon as I got my new laptop, I was foolish enough not to think ahead and deleted the preinstalled Windows 8 to install my usual setup with Linux Mint. As I need Windows for testing web pages, I need a working genuine installation, but there was no sticker with the product key this time.
As it turns out, Windows 8 uses a new way to keep the product key safe - it is embedded in the bios. This is great, as Samsung support told me that by repartitioning the hard drive I lost all claims for windows and I have to buy it again.
Now all I have to do is get the key. Some googling later I found that the RWEverything program can possibly do this. It's worth a try at least.
Download RWEverything here: http://rweverything.com/download/
Info source: http://www.nextofwindows.com/how-to-retrieve-windows-8-oem-product-key-from-bios/