If it can help others, I did the following steps to solve the USB access denied message on Ubuntu.
I installed the Android SDK Platform Tools (which has probably nothing to do with the issue)
I enabled the permission "Access USB hardware directly" for Brave from the settings in the OS.