The labyrinth isn't randomly generated, somewhere in the dungeon there is a switch that opens the gate to the red box. The first time I missed it but if you go into a room and search it, a "lotah" is in the corner, that is a switch. If you check what you can do in the room, it tells you that you can flip the switch.

thanks