To receive this quest, you first need to complete the "Darkness in the Lighthouse" quest. You will receive it from Naga, whom you have rescued at the lighthouse's exit.
You need to go South a bit, to the sea harbor, over the bridge ( there is a field inn past the bridge, where you can buy 20 supplies) and then, to the West, next to Karthal. Cross the Halloth grove fragment. After a while, you should notice a desert named ravaged Lands. To the South-West of the Sea Harbor. The location that you are going to is called "Skull Rock" (1) and it is close to the location where the meteorite fell in the "Fallen Star" quest. If you are currently in the city of Crag, you simply need to go Southwards a bit. At the entrance, there is a single Kenshi waiting and by that, you will tell that you are finally there.
Inside(2) you will find a multitude of Priestesses, Commanders and Kenshi. You can go for the passage to the next level immediately (3) or dig up a key for a treasure chest. Watch put, however, because you will respawn eight enemies, as soon as you open the chest at this level and this will be a hard way through. Remember to kill Priestesses in the first place, if it comes to pass, because they cast AoE spells. Kenshi and commanders are not that tough, if they fail to block many of your attacks so, you can leave them for later.
The password to the second level is: Swordfish.
Downstairs(4), it is going to be more difficult than it has been so far, because you will be encountering Elite enemies. You can go North first and collect the mysterious box (it pays off) of the Blackfang (necessary for the "Partners in Crime" quest) from the chest. You can also go South (5) to another room, where you find the sword that you are looking for. You can also do both and kill the boss, while you are here, who is in the center (for the "Grand Master of Archery" quest). Just be careful because, as soon as you touch any of the chests at this level, there will appear a multitude of enemies behind your back. You need to remember that these enemies are immune to mind tricks so, attacks like Summon or Head Split are useless.