What a great challenge! I ironically found the tool required after solving it. Initially gave up trying to find the tool and ended up watching a few DNS exfiltration videos on youtube which showed a few of the common encoding techniques used. I then used CyberChef with two recipes, tweaking a few of the characters to comply with base64 first, then piped that into the second one, which gave something obvious (and magical). Happy to give some nudges.
- Understanding what the allowed characters are in both base64 and a domain name will help.
- as will the 2nd encoding used