Carnivale Intrigue is written in the key of A Phrygian.
According to the Theorytab database, it is the 3rd most popular key among Phrygian keys and the 51st most popular among all keys. The A Phrygian scale is similar to the A Minor scale except that its 2nd note (B♭) is a half step lower. Chord progressions in Phrygian often rely on the major chord built off of this 2nd scale degree (B♭ major) which gives the key its distinctive sound.
See the A Phrygian Cheat Sheet for popular chords, chord progressions, downloadable midi files and more!