Windows – Every windows 8 boot breaks grub

You're looking for "efibootmgr". This program can be used on a GNU/Linux system that has booted into EFI mode (so use a live disk or something to get to it).

It has a few switches, and is generally pretty simple. You're looking to create an EFI boot entry, and also view existing entries.

You can view the existing boot entries with "efibootmgr -v". This will reveal either a lack of an EFI entry, or perhaps a malformed EFI entry.

If you have an entry already, or if there is nothing there at all, rebuilding the GRUB should invoke efibootmgr to create an entry for you. This is the easiest course of action. You should do this within a chroot of your already installed system (another reason why we're using a live system). If you don't know how to set up a chroot environemnt, please reference this guide: https://help.ubuntu.com/community/BasicChroot

After that is done, reinstall the GRUB package:

sudo apt-get install --reinstall grub-efi

Once that is complete, stick the GRUB on your disk again:

sudo grub-install /dev/sda

Re-create your GRUB config (this should invoke efibootmgr as well):

sudo update-grub

Check that you have EFI boot images in /boot/EFI for your linux install. You should have directories for both Windows and Linux side by side, with .efi files in each.

Finally, check that you have a proper boot entry in your EFI NVRAM using efibootmgr -v

If you still don't have one, can verify that you have the .efi files in a mounted FAT filesystem on /boot/EFI and then create the entry yourself. This is where things get a little odd for me to describe here, but the efibootmgr man page is very helpful: http://linux.die.net/man/8/efibootmgr

EDIT: More info on manually creating an EFI entry:

Since the automatic GRUB steps don't appear to have helped in your case, let's make an entirely new EFI entry that will point to your GRUB binary. We'll use efibootmgr for this.

Thanks to the information you provided, we can make a command that should work for you in a copy/paste capacity. Cool. Before you begin with this, get into a chroot env on your native system from an EFI booted live one just as suggested above. Also, mount your EFI filesystem to /boot/efi within the chroot.

This can be accomplished with one command (tailored for your situation):

efibootmgr -c -l \\EFI\\ubuntu\\shimx64.efi -L UbuntuBoot

This is a secureboot (that's what shimx64 is) EFI entry that points to the GRUB binary (rather than the default, which would be elilo.efi - which you don't have), has a cosmetic name of UbuntuBoot (to differentiate from the others), and will use /dev/sda and /dev/sda1 both as the disk and partition respectively. This is default for efibootmgr -c, so if you had the EFI filesystem on a different disk or partition, you'd have to specify explicitly via options. The backslashes have to be escaped with backslashes to be "literal".

Once you've created that entry, you should be able to see it via efibootmgr -v. If it's there, try booting into it. If you can boot into it, you should probably delete the old ones.

This kind of problem when installing Windows is common, but only if you choose to install the EFI binaries to the "removable disk EFI region" of your drive. Only one EFI entry may go there, and that is the region Windows uses no matter what to accomplish EFI booting. We typically only use that area on buggy EFI systems that won't boot any other way, but it is guaranteed to work on anything.

However, installing another EFI enabled OS on that same area will blow your previously installed EFI binary away. When installing most Linux distros, it will typically ask if you want to force GRUB installation to the "Removable media path" for EFI. Choose no, and this scenario shouldn't happen again. It isn't necessary to use the removable media path on just about any modern EFI.