If you start a rebellion with a claimant you are automatically at war with the corresponding faction.
If you attack faction units (easiest are caravans) your relation will decrease. With trading caravans the decrease will happen during conversation, that way if you just use that topic repeatedly with the same caravan you can go to war with anyone. I don't remember the needed conversation topic, just try it.