Key # 1
Location: Pyramid Falls
Enter the cave near Pyramid Falls. The key is in a chest inside.
Key # 2
Location: Victory Beach
Inside a cave near Victory Beach blocked by a large stone there is a room with a bombable wall. In the next room, step across the spikes and walk through the fake door. The key is in the chest in the next room.
Key # 3
Location: Halls of Pain (Secret Meadow)
In the Halls of Pain, located in the Secret Meadow, bomb jump straight up the east-most path to reach a chest containing the key.
Key # 4
Location: Church Basement
Enter the basement of the church in the Icy World and press X + R to reveal a secret path that will lead you to a chest containing the key.
Key # 5
Location: Icy Beach
Enter the northmost cave near the Icy Beach and in the room northwest of the entrance you will find a chest behind two spikes. Press X + R to reveal a path to the chest.
Key # 6
Location: Lake Ruins
Enter the cave in the north-east section of the Lake Ruins and you will find yourself in a house with a talking tree-creature. Press X + R to reveal a bombable wall. Bomb the wall and walk through to find a key under a skull in the next room.
Key # 7
On the 3rd floor of the Parallel Tower, after beating Moldorm, a door will open to the west. Through that door is a large stone. Pick up the stone and continue south. In this room, there is an invisible floor with a gap that you can bomb-jump across. The key is under the southeast skull. Alternatively, if you have trouble with the bomb-jump, you can fall through a hole in the floor on the 5th floor in the room with a fire blade southeast of the stairs. Fall through the central hole directly below the door and you will find yourself in the southern portion of the Beamos maze. Head west through the cracked wall and you will find yourself in the same room but on the other side of the gap.
Key # 8
Go south in the room immediately after fighting the Armos Knights and you will see the key on a platform across a large gap. Wait for the floor tiles to finish flying at you and the path to the key will be revealed.
Key # 9
Under a skull in a room you must pass through on the 6th floor.