In case anyone is still stuck on this, i followed the instructions from Frederic Dufour but still didn't work, here is what I was missing and needed to do to get it to work.
Got to settings > click on your apple ID
click on "iCloud" > the section labeled "Apps using iCloud" click the "SHOW ALL" option
this will list all the apps using iCloud, find authenticator on that list and switch it ON
Then, go back to "iCloud Drive" > switch it to ON
Now go back to Authenticator and turn on back ups and it should work