Time Machine stopped recognising backups on the NAS storage and does not make new backups anymore I have a disk that is attached as a NAS storage to Time Machine. It's just a hard drive connected to my router.
I started doing Time Machine backups to this disk rather recently and until several days ago backups were done without any problems. But now Time Machine complains about incorrect credentials (based on what it tells me) and for some reason no backups are found on this disk anymore.
I tried to add and remove the storage many times and run a few commands with tmutil but without a deep understanding how it works it's hard to fix anything or even find out the cause of the problem...
This is what it looks like:

I start with a pristine and uninitialized Time Machine screen and there I select the NAS storage.

It asks me to provide credentials for the NAS storage.

After entering the correct credentials it says that there is an existing encrypted backup already and asks me if I want to use it or start over:


After I click on Use Existing Backup button it asks me to provide a password for my existing backup, and that's where things become interesting... I know the correct password but whatever I enter the result is the same.

At first it shows that there are no backups on the disk:


Then it starts looking for the backup disk:


And then a popup shows up saying that &quot;The network backup disk could not be accessed because there was a problem with the username or password&quot;:



But the credentials are ok. Whenever I try to open the .sparsebundle file on that disk (even when it is connected directly to my MacBook) it is mounted successfully and I can browse all snapshots without even typing the encryption password (which I find particularly weird because KeyChain on my MacBook does not contain any keys which are related to the backups - I removed everything intentionally to check if that will work).
And this is what happens when I try to run most of the commands with tmutil:
 ~ % tmutil machinedirectory
 No machine directory found for host.

 ~ % tmutil latestbackup
 Unable to locate machine directory for host.

Any suggestions?
UPD:
I figured out why my Time Machine sparsebundle didn't require password. It was saved in KeyChain but under some strange GUID with the suffix/extension &quot;.sparsebundle&quot;. I found it by searching &quot;disk&quot;. And then after I removed these items completely I need to enter the password every time I access the sparsebundle image.
And... After playing around with tmutil associatedisk I managed to change the behavior of Time Machine. Now, instead of accepting any password and then displaying that there are no backups found, it rejects any password and says that &quot;Password is invalid&quot; although the password is obviously correct assuming that I can access the sparsebundle contents directly through Finder.
So it seems that the problem is related to my router or one of the recent MacOS upgrades that probably introduced something new or broke compatibility because just weeks ago it worked properly. Just for the record the model of my router is Keenetic Giga.
How did I understand it? I created a blank HFS+ partition, connected my HDD to the router and fed it up to Time Machine. I got the same error as described in my question. So it is clear that the cause of the error is not associated with the backup itself.
So I decided to migrate all my backups to a new partition on that drive and use it as a local backup storage instead of NAS. And because I had that .sparsebundle file I needed to figure out a way to &quot;burn&quot; it (copy its contents) to the new APFS volume. It seemed like an easy task to do but it's really not...
I'll skip a story with all my tries and failures and move directly to the solution.
So to convert a .sparsebundle file to APFS volume there is a feature called &quot;Restore&quot; in the Disk Utility. But UI is not much helpful because in general this functionality sucks when it comes to the .sparsebundle format. So we need to arm ourselves with patience and Terminal. And at first we need to mount the &quot;.sparsebundle&quot; image through Finder and then change metadata of the mounted volume a little:
diskutil apfs changeVolumeRole /dev/diskXsY t
where diskXsY - is the identifier of your volume which you can find running diskutil apfs list

This command will change the role of your volume and MacOS will no longer know that it is a backup storage. Without doing it the next command will fail (due to a bug).
sudo asr restore --source /Volumes/EXTERNAL_HDD/{the name of your computer}.sparsebundle --noverify  --target /dev/diskAsB --erase  --debug --verbose
where /dev/diskAsB is the identifier of a volume that you want to use as the backup storage. 
--noverify is needed here because there is also another bug in this utility.

After you enter a password (if you have an encrypted backup) and agree to erase the volume this command will replicate the contents of your &quot;.sparsebundle&quot; onto the target volume. It will take a while...
After it finishes you will almost receive a functional (unencrypted) backup storage. To make it fully functional you should run:
diskutil apfs changeVolumeRole /dev/diskAsB T

This command will assign a Backup role to your target volume and Time Machine will recognize it.
Later you may want to encrypt your storage with &quot;hdiutil&quot; (warning: it will take hours to complete).
At this stage I configured Time Machine to use the drive as a local backup storage and after doing that one of the folders changed its suffix in the name from .inprogress to .interrupted.
At the end of the day Time Machine copied an increment only and it looked like this:


After the backup process finished I looked into the contents of the drive and found out that Time Machine killed my old backups and during the Cleaning up phase it went from this:
$ ... % ls
2021-05-06-201324.previous  2021-05-22-195414.inprogress
2021-05-06-212814.interrupted   backup_manifest.plist

to this:
$ ... % ls
2021-05-22-212814.previous  backup_manifest.plist

I believe that it is due to the interrupted backup which you can see above but I don't want to spend any more time on that. So technically I still didn't get my old backups back and all I got was pain from multiple Apple bugs and inconveniences but at least I have more knowledge now how it is built under the hood and probably this information will be useful for someone who want to convert .sparsebundle to APFS (or to be more concise - to a local backup disk formatted as APFS).